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.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
import java.io.*;
public class Main {
    // Graph
    // prefix sums
    //inputs
    public static void main(String args[])throws Exception{
        Input sc=new Input();
        precalculates p=new precalculates();
        StringBuilder sb=new StringBuilder();
        int t=sc.readInt();
        for(int f=0;f<t;f++){
            long n=sc.readLong();
            //long l=1,r=
            pair pp=primeFactors(n,0,n);
            //System.out.println(pp.gcd+" "+pp.val);
            int a=pp.gcd+pp.gcd;
            int b=pp.gcd*(pp.val-3);
            int c=pp.gcd;
            if(a>0 && b>0 && c>0)
            sb.append(a+" "+b+" "+c+"\n");
            else {
                if(n%2==0)
                    sb.append(((n-1)/2-1) + " " + (1 +(n-1)/2) + " " + 1 + "\n");
                else{
                    sb.append(((n-1)/2-1) + " " + (1 +(n-1)/2) + " " + 1 + "\n");
                }
            }
        }
        System.out.print(sb);
    }

    public static pair primeFactors(long n,long c,long tar)
    {
        precalculates p=new precalculates();
        HashSet<Long> set=new HashSet<>();
        while (n%2==0)
        {
            //System.out.print(2 + " ");
            if(tar%2==0){
                long val=n/2;
                if(val>=6){
                    if(p.gcd(4,tar-6)==2)
                    return new pair((int)val,2);
                }
            }
            n /= 2;
        }


        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            while (n%i == 0)
            {
                //System.out.print(i + " ");
                if(tar%i==0){
                        long val=tar/i;
                        if(val>=6){
                            if(p.gcd(2*i,tar-3*i)==i)
                            return new pair((int)val,i);
                        }

                }
                n /= i;
            }
        }

        if (n > 2) {
            if (tar % n == 0) {
                long val = tar / n;
                if (val >= 6) {
                    if(p.gcd(2*n,tar-3*n)==n)
                    return new pair((int)val,(int)n);
                }

            }
        }

        return new pair(-1,-1);
    }
}
class pair{
    int val;
    int gcd;

    public pair(int val, int gcd) {
        this.val = val;
        this.gcd = gcd;
    }
}
class Input{
    BufferedReader br;
    StringTokenizer st;
    Input(){
        br=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
    }
    public int[] readArray() throws Exception{
        st=new StringTokenizer(br.readLine());
        int a[]=new int[st.countTokens()];
        for(int i=0;i<a.length;i++){
            a[i]=Integer.parseInt(st.nextToken());
        }
        return a;
    }
    public long[] readArrayLong() throws Exception{
        st=new StringTokenizer(br.readLine());
        long a[]=new long[st.countTokens()];
        for(int i=0;i<a.length;i++){
            a[i]=Long.parseLong(st.nextToken());
        }
        return a;
    }
    public int readInt() throws Exception{
        st=new StringTokenizer(br.readLine());
        return Integer.parseInt(st.nextToken());
    }
    public long readLong() throws Exception{
        st=new StringTokenizer(br.readLine());
        return Long.parseLong(st.nextToken());
    }
    public String readString() throws Exception{
        return br.readLine();
    }
    public int[][] read2dArray(int n,int m)throws Exception{
        int a[][]=new int[n][m];
        for(int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                a[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        return a;
    }
}
class precalculates{
    public long gcd(long p, long q) {
        if (q == 0) return p;
        else return gcd(q, p % q);
    }
    public int[] prefixSumOneDimentional(int a[]){
        int n=a.length;
        int dp[]=new int[n];
        for(int i=0;i<n;i++){
            if(i==0)
                dp[i]=a[i];
            else
                dp[i]=dp[i-1]+a[i];
        }
        return dp;
    }
    public int[] postSumOneDimentional(int a[]) {
        int n = a.length;
        int dp[] = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            if (i == n - 1)
                dp[i] = a[i];
            else
                dp[i] = dp[i + 1] + a[i];
        }
        return dp;
    }
    public int[][] prefixSum2d(int a[][]){
        int n=a.length;int m=a[0].length;
        int dp[][]=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=a[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
            }
        }
        return dp;
    }
    public long pow(long a,long b){
        long mod=1000000007;
        long ans=0;
        if(b<=0)
            return 1;
        if(b%2==0){
            ans=pow(a,b/2)%mod;
            return ((ans%mod)*(ans%mod))%mod;
        }else{
            return ((a%mod)*(ans%mod))%mod;
        }
    }

}
class GraphInteger{
    HashMap<Integer,vertex> vtces;
    class vertex{
        HashMap<Integer,Integer> children;
        public vertex(){
            children=new HashMap<>();
        }
    }
    public GraphInteger(){
        vtces=new HashMap<>();
    }
    public void addVertex(int a){
        vtces.put(a,new vertex());
    }
    public void addEdge(int a,int b,int cost){
        if(!vtces.containsKey(a)){
            vtces.put(a,new vertex());
        }
        if(!vtces.containsKey(b)){
            vtces.put(b,new vertex());
        }
        vtces.get(a).children.put(b,cost);
//        vtces.get(b).children.put(a,cost);
    }
    public boolean isCyclicDirected(){
        boolean isdone[]=new boolean[vtces.size()+1];
        boolean check[]=new boolean[vtces.size()+1];
        for(int i=1;i<=vtces.size();i++) {
            if (!isdone[i] && isCyclicDirected(i,isdone, check)) {
                return true;
            }
        }
        return false;
    }
    private boolean isCyclicDirected(int i,boolean isdone[],boolean check[]){
        if(check[i])
            return true;
        if(isdone[i])
            return false;
        check[i]=true;
        isdone[i]=true;
        Set<Integer> set=vtces.get(i).children.keySet();
        for(Integer ii:set){
            if(isCyclicDirected(ii,isdone,check))
                return true;
        }
        check[i]=false;
        return false;
    }
}
class union_find {
    int n;
    int[] sz;
    int[] par;

    union_find(int nval) {
        n = nval;
        sz = new int[n + 1];
        par = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int x) {
        if (par[x] == x)
            return x;
        return par[x] = root(par[x]);
    }

    boolean find(int a, int b) {
        return root(a) == root(b);
    }

    int union(int a, int b) {
        int ra = root(a);
        int rb = root(b);
        if (ra == rb)
            return 0;
        if(a==b)
            return 0;
        if (sz[a] > sz[b]) {
            int temp = ra;
            ra = rb;
            rb = temp;
        }
        par[ra] = rb;
        sz[rb] += sz[ra];
        return 1;
    }
}






