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 cf {
 
    public static void main(String[] args){
 
        FastScanner sc = new FastScanner();
        int x = sc.nextInt();
        //int x=1;
        while(x-- > 0){
            /*int n=sc.nextInt();
            //int m=sc.nextInt();
            int arr[]=new int[n];
            for(int i=0;i<n;i++){
                arr[i]=sc.nextInt();
            }*/
            int n=sc.nextInt();
            if(n%2==0){
                System.out.println((n-3)+" "+2+" "+1);
            }
            else{
                //System.out.println(()+" "+()+" "+1)
                n=n-1;
                int y=n/2;
                if(y%2==1){
                    System.out.println((y-2)+" "+(y+2)+" "+1);
                }
                else{
                    System.out.println((y-1)+" "+(y+1)+" "+1);

                }
            }
            
            

            






            
            



            
            

        }
        

    }
    public static long gcd(long a,long b){
        if(b == 0){
            return a;
        }
        return gcd(b,a%b);
    }               
            
}
/////////////////////////////////////////////////////////////
//BINARY SEARCH
/*Arrays.binarySearch(arr,key);
if key--> present 
    return index
else 
    return -(index where it would be inserted)-1*/


//////////////////////////////////////////////////////////////
 


/*  VALUE JUST GREATER THAN X  
 find_min(int[]arr,int x){
    int l=-1;
    int r=arr.length;
    while(r>l+1){
        int mid=(l+r)/2;
        if(arr[mid]<x){
            l=mid;
        }
        else{
            r=mid;
        }
    }
    return r;
 }
    VALUE JUST SMALLER THAN X
  find_max(int[]arr,int x){
    int l=-1;
    int r=arr.length;
    while(r>l+1){
        int mid=(l+r)/2;
        if(arr[mid]<=x){
            l=mid;
        }
        else{
            r=mid;
        }
    }
    return l;
 }  
   */ 
    
 


//////////////////////////////////////////////////////////////
// LCM AND GCD
/*
    public static int gcd(int a,int b){
        if(b == 0){
            return a;
        }
        return gcd(b,a%b);
    }
 
    public static int lcm(int a,int b){
         return (a / gcd(a, b)) * b;
    }*/


///////////////////////////////////////////////////////////////////////////////////

//Iterator



/*Iterator iterator = object.iterator();
 
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + " ");
        }*/
///////////////////////////////////////////////////////////////////////////////////


class FastScanner
{
    //I don't understand how this works lmao
    private int BS = 1 << 16;
    private char NC = (char) 0;
    private byte[] buf = new byte[BS];
    private int bId = 0, size = 0;
    private char c = NC;
    private double cnt = 1;
    private BufferedInputStream in;
 
    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }
 
    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        } catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }
 
    public char getChar() {
        while (bId == size) {
            try {
                size = in.read(buf);
            } catch (Exception e) {
                return NC;
            }
            if (size == -1) return NC;
            bId = 0;
        }
        return (char) buf[bId++];
    }
 
    public int nextInt() {
        return (int) nextLong();
    }
 
    public int[] nextInts(int N) {
        int[] res = new int[N];
        for (int i = 0; i < N; i++) {
            res[i] = (int) nextLong();
        }
        return res;
    }
 
    public long[] nextLongs(int N) {
        long[] res = new long[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextLong();
        }
        return res;
    }
 
    public long nextLong() {
        cnt = 1;
        boolean neg = false;
        if (c == NC) c = getChar();
        for (; (c < '0' || c > '9'); c = getChar()) {
            if (c == '-') neg = true;
        }
        long res = 0;
        for (; c >= '0' && c <= '9'; c = getChar()) {
            res = (res << 3) + (res << 1) + c - '0';
            cnt *= 10;
        }
        return neg ? -res : res;
    }
 
    public double nextDouble() {
        double cur = nextLong();
        return c != '.' ? cur : cur + nextLong() / cnt;
    }
 
    public double[] nextDoubles(int N) {
        double[] res = new double[N];
        for (int i = 0; i < N; i++) {
            res[i] = nextDouble();
        }
        return res;
    }
 
    public String next() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c > 32) {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }
 
    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while (c <= 32) c = getChar();
        while (c != '\n') {
            res.append(c);
            c = getChar();
        }
        return res.toString();
    }
 
    public boolean hasNext() {
        if (c > 32) return true;
        while (true) {
            c = getChar();
            if (c == NC) return false;
            else if (c > 32) return true;
        }
    }
}

