Given a positive integer n. Find three distinct positive integers a, b, c such that a + b + c = n and \operatorname{gcd}(a, b) = c, where \operatorname{gcd}(x, y) denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers x and y.

Input

The input consists of multiple test cases. The first line contains a single integer t (1 ≤ t ≤ 10^5) — the number of test cases. Description of the test cases follows.

The first and only line of each test case contains a single integer n (10 ≤ n ≤ 10^9).

Output

For each test case, output three distinct positive integers a, b, c satisfying the requirements. If there are multiple solutions, you can print any. We can show that an answer always exists.

Example

Input


6
18
63
73
91
438
122690412


Output


6 9 3
21 39 3
29 43 1
49 35 7
146 219 73
28622 122661788 2

Note

In the first test case, 6 + 9 + 3 = 18 and \operatorname{gcd}(6, 9) = 3.

In the second test case, 21 + 39 + 3 = 63 and \operatorname{gcd}(21, 39) = 3.

In the third test case, 29 + 43 + 1 = 73 and \operatorname{gcd}(29, 43) = 1.
1
669278611
 10
10
52
91
23
44
99
28
54
99
51

334639303 334639307 1
 4 5 1
25 26 1
43 47 1
9 13 1
21 22 1
47 51 1
13 14 1
26 27 1
47 51 1
23 27 1

import java.io.*;
import java.util.*;

public class q2 {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//    public static long mod = 1000000007;

    static boolean[] primes;
    public static void fill(){
        for(int i = 2;i < primes.length;i++) primes[i] = true;

        for(int i = 2;i * i < primes.length;i++){
            if(primes[i]){
                for(int j = i * i;j < primes.length;j += i){
                    primes[j] = false;
                }
            }
        }
    }
    public static void solve() throws Exception {
        int n = Integer.parseInt(br.readLine());

        for(int i = 2;i < n;i++){
            int a = i;
            int c = 1;
            int b = n - a - c;

            if(primes[a] && b % a != 0){
                System.out.println(a + " " + b + " " + c);
                return;
            }
        }

    }

    public static void main(String[] args) throws Exception {
        primes = new boolean[100000];
        fill();
        int tests = Integer.parseInt(br.readLine());
        for (int test = 1; test <= tests; test++) {
            solve();
        }
    }

//    public static void sort(int[] arr){
//        ArrayList<Integer> temp = new ArrayList<>();
//        for(int val : arr) temp.add(val);
//
//        Collections.sort(temp);
//
//        for(int i = 0;i < arr.length;i++) arr[i] = temp.get(i);
//    }
//    public static void sort(long[] arr){
//        ArrayList<Long> temp = new ArrayList<>();
//        for(long val : arr) temp.add(val);
//
//        Collections.sort(temp);
//
//        for(int i = 0;i < arr.length;i++) arr[i] = temp.get(i);
//    }
//
//    public static long power(long a,long b,long mod){
//        if(b == 0) return 1;
//
//        long p = power(a,b / 2,mod);
//        p = (p * p) % mod;
//
//        if(b % 2 == 1) return (p * a) % mod;
//        return p;
//    }
//
//    public static int GCD(int a,int b){
//        return b == 0 ? a : GCD(b,a % b);
//    }
//    public static long GCD(long a,long b){
//        return b == 0 ? a : GCD(b,a % b);
//    }
//
//    public static int LCM(int a,int b){
//        return a * b / GCD(a,b);
//    }
//    public static long LCM(long a,long b){
//        return a * b / GCD(a,b);
//    }
}
