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.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;



public class a729 {

	public static void main(String[] args) throws IOException {
       BufferedWriter out = new BufferedWriter(
	            new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(
		        new InputStreamReader(System.in));
		PrintWriter pt = new PrintWriter(System.out);
		FastReader sc = new FastReader();

		int t = sc.nextInt();
		for(int o = 0 ; o<t;o++){
		
		int n = sc.nextInt();
		if(n%2==0) {
			int x = n/2 - 1;
			int y= n/2;
			System.out.println(x + " " + y + " " + 1);
		}else {
			if((n/2)%2==0) {
				int a = n/2 + 1;
				int b = n/2 - 1;
				int c = 1;
			System.out.println(a + " " + b + " " + c);
			}else {
				int a = n/2 + 2;
				int b = n/2 - 2;
				int c = 1;
				System.out.println(a + " " + b + " " + c);
			}
		}
		
			
			
		}
	}
//------------------------------------------------------------------------------------------------------------------------------------------------
	
	
	
	public static long findgcd(long[] arr,int v) {
		int n = arr.length;
		long g = arr[v];
		for(int i = v ; i<n;i+=2) {
			g = gcd(g, arr[i]);
		}
		return g;
	}
	
	
	
	
	
	
	
	
	
	
	public static int count(long x) {
		int a = 0;
		while(x>0) {
			x/=2;
			a++;
		}
		return a;
		
	}
	

	public static long ncr(long[] fac, int n , int r , long m) {
		return fac[n]*(modInverse(fac[r], m))%m *(modInverse(fac[n-r], m))%m; 
	}
	
	
	public static void build(int [][] seg,char []arr,int idx, int lo , int hi) {
	if(lo == hi) {
//		seg[idx] = arr[lo];
		seg[idx][(int)arr[lo]-'a'] = 1;
		
		return;
	}
	int mid = (lo + hi)/2;
build(seg,arr,2*idx+1, lo, mid);
build(seg,arr,idx*2+2, mid +1, hi);
//seg[idx] = Math.min(seg[2*idx+1],seg[2*idx+2]);
for(int i = 0 ; i<27;i++) {
	seg[idx][i] = seg[2*idx+1][i] + seg[2*idx + 2][i];
}
	}
//for f/inding minimum in range 
public static void query(int[][]seg,int[]ans,int idx , int lo , int hi , int l , int r) {
	if(lo>=l && hi<=r) {
		for(int i = 0 ; i<27;i++) {
			ans[i]+= seg[idx][i];
		}
		return ;
	}
if(hi<l || lo>r) {
	return;
}
int mid = (lo + hi)/2;
query(seg,ans,idx*2 +1, lo, mid, l, r);
query(seg,ans,idx*2 + 2, mid + 1, hi, l, r);
//return Math.min(left, right);
}
//// for sum
//
public static void update(int[][]seg,char[]arr,int idx, int lo , int hi , int node , char val) {
if(lo == hi) {
//	seg[idx] += val;
seg[idx][val-'a']++;
seg[idx][arr[node]-'a']--;

}else {
int mid = (lo + hi )/2;
if(node<=mid && node>=lo) {
update(seg,arr, idx * 2 +1, lo, mid, node, val);
}else {
update(seg,arr, idx*2 + 2, mid + 1, hi, node, val);
}
//seg[idx] = seg[idx*2 + 1] + seg[idx*2 + 2];
for(int i = 0 ; i<27;i++) {
	seg[idx][i] = seg[2*idx+1][i] + seg[2*idx + 2][i];
}
}

}
	
	
	
	
	
	
	public static int lower_bound(int array[], int low, int high, int key){
	// Base Case
	if (low > high) {
	return low;
	}

	// Find the middle index
	int mid = low + (high - low) / 2;

	// If key is lesser than or equal to
	// array[mid] , then search
	// in left subarray
	if (key <= array[mid]) {

	return lower_bound(array, low,
	            mid - 1, key);
	}

	// If key is greater than array[mid],
	// then find in right subarray
	return lower_bound(array, mid + 1, high,
	        key);
	}
	
	public static int upper_bound(int arr[], int low,
            int high, int key){
// Base Case
if (low > high || low == arr.length)
return low;

// Find the value of middle index
int mid = low + (high - low) / 2;

// If key is greater than or equal
// to array[mid], then find in
// right subarray
if (key >= arr[mid]) {
return upper_bound(arr, mid + 1, high,
                key);
}

// If key is less than array[mid],
// then find in left subarray
return upper_bound(arr, low, mid - 1,
            key);
}

//	-----------------------------------------------------------------------------------------------------------------------------------------------
	public static long gcd(long a, long b){
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
//--------------------------------------------------------------------------------------------------------------------------------------------------------
	public static long modInverse(long a, long m){
        long m0 = m;
        long y = 0, x = 1;
 
        if (m == 1)
            return 0;
 
        while (a > 1) {
            // q is quotient
            long q = a / m;
 
            long t = m;
 
            // m is remainder now, process
            // same as Euclid's algo
            m = a % m;
            a = t;
            t = y;
 
            // Update x and y
            y = x - q * y;
            x = t;
        }
 
        // Make x positive
        if (x < 0)
            x += m0;
 
        return x;
    }

		

//-----------------------------------------------------------------------------------------------------------------------------------

	//segment tree
	//for finding minimum in range 
//	public static void build(int [] seg,int []arr,int idx, int lo , int hi) {
//		if(lo == hi) {
//			seg[idx] = arr[lo];
//			return;
//		}
//		int mid = (lo + hi)/2;
//	build(seg,arr,2*idx+1, lo, mid);
//	build(seg,arr,idx*2+2, mid +1, hi);
//	seg[idx] = Math.min(seg[2*idx+1],seg[2*idx+2]);
//	}
////for finding minimum in range 
//public static int query(int[]seg,int idx , int lo , int hi , int l , int r) {
//		if(lo>=l && hi<=r) {
//			return seg[idx];
//		}
//	if(hi<l || lo>r) {
//		return Integer.MAX_VALUE;
//	}
//	int mid = (lo + hi)/2;
//	int left = query(seg,idx*2 +1, lo, mid, l, r);
//	int right = query(seg,idx*2 + 2, mid + 1, hi, l, r);
//	return Math.min(left, right);
//}
//	// for sum
//
//public static void update(int[]seg,int idx, int lo , int hi , int node , int val) {
//	if(lo == hi) {
//		seg[idx] += val;
//	}else {
//int mid = (lo + hi )/2;
//if(node<=mid && node>=lo) {
//	update(seg, idx * 2 +1, lo, mid, node, val);
//}else {
//	update(seg, idx*2 + 2, mid + 1, hi, node, val);
//}
//seg[idx] = seg[idx*2 + 1] + seg[idx*2 + 2];
//
//}

//}
//---------------------------------------------------------------------------------------------------------------------------------------


	static void shuffleArray(int[] ar)
	  {
	    // If running on Java 6 or older, use `new Random()` on RHS here
	    Random rnd = ThreadLocalRandom.current();
	    for (int i = ar.length - 1; i > 0; i--)
	    {
	      int index = rnd.nextInt(i + 1);
	      // Simple swap
	      int a = ar[index];
	      ar[index] = ar[i];
	      ar[i] = a;
	    }
	  }
//-----------------------------------------------------------------------------------------------------------------------------------------------------------

}


class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader()
    {
        br = new BufferedReader(
            new InputStreamReader(System.in));
    }

    String next()
    {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());

            
            
            
            
            }
            catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() { return Integer.parseInt(next()); }

    long nextLong() { return Long.parseLong(next()); }

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    String nextLine()
    {
        String str = "";
        try {
            str = br.readLine();
        }
        catch (IOException e) {
            e.printStackTrace();
        }
        return str;
    }
}
//------------------------------------------------------------------------------------------------------------------------------------------------------------
class SegmentTree{
	
int n;
	public SegmentTree(int[] arr,int n) {
		this.arr = arr;
		this.n = n;
	}
	int[] arr = new int[n];
//	int n = arr.length;
	int[] seg = new int[4*n];
	void build(int idx, int lo , int hi) {
		if(lo == hi) {
			seg[idx] = arr[lo];
			return;
		}
		int mid = (lo + hi)/2;
	build(2*idx+1, lo, mid);
	build(idx*2+2, mid +1, hi);
	seg[idx] = Math.min(seg[2*idx+1],seg[2*idx+2]);
	}
	int query(int idx , int lo , int hi , int l , int r) {
		if(lo<=l && hi>=r) {
			return seg[idx];
		}
	if(hi<l || lo>r) {
		return Integer.MAX_VALUE;
	}
	int mid = (lo + hi)/2;
	int left = query(idx*2 +1, lo, mid, l, r);
	int right = query(idx*2 + 2, mid + 1, hi, l, r);
	return Math.min(left, right);
	}
	
	
}
//-----------------------------------------------------------------------------------------------------------------------------------------------------------
class coup{
	char a; 
	int b;
	public coup(char a , int b) {
		this.a = a;
		this.b = b;
	}
}

class trip{
	int a , b, c;
	public trip(int a , int b, int c) {
		this.a = a;
		this.b = b;
		this.c = c;
	}
}
//---------------------------------------------------------------------------------------------------------------------------------------------------------------
