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.util.*;
import java.io.*;

public class path {

	static boolean check(long d, long[] arr) {
		if (d == 0)
			return true;
		for (int i = 1; i < arr.length; i++) {
			if (arr[i - 1] % d == 0 && arr[i] % d == 0)
				return false;
			if (arr[i - 1] % d != 0 && arr[i] % d != 0)
				return false;
		}
		return true;
	}

	static long gcd(long a, long b) {
		if (b == 0)
			return a;
		else
			return gcd(b, a % b);
	}

	/*
	 * static long binarySearch(long start, long end, long [] arr){ if(arr.length ==
	 * 2) return Math.max(arr[0], arr[1]);
	 * 
	 * while(start < end){ long mid = (start + end) / 2; if(check(mid, arr)){ ans =
	 * mid; start = mid + 1; } else end = mid; }
	 * 
	 * for(int i = 0; i < arr.length - 2; i += 2) { long p = gcd(arr[i], arr[i +
	 * 2]); if(p != 1) { if(check(p, arr)) return p; } } for(int i = 1; i <
	 * arr.length - 2; i += 2) { long p = gcd(arr[i], arr[i + 2]); if(p != 1) {
	 * if(check(p, arr)) return p; } } return 0; }
	 */
	static int seq(int [] arr, int index, int len) {
		int ans = 0;;
		for(int i = 0; i < len; i++) {
			if((index & (1 << i)) != 0) {
				ans = ans ^ arr[i];
			}
		}
		return ans;
	}
	static boolean isPrime(long n) {
		if(n == 1) return false;
		if(n % 2 == 0 || n % 3 == 0) return false;
		for(int i = 5; i * i <= n; i+= 6) {
			if(n % i == 0 || n % (i + 2) == 0) return false;
		}
		return true;
	}
	static int subSeq(int [] arr) {
		int n = arr.length;
		int ans = 0;
		int max = 0;
		long limit = (long) (Math.pow(2, n) - 1);
		for(int i = 1; i <= limit; i++) {
			max = Math.max(seq(arr, i, n), max);
		}
		for(int i = 1; i <= limit; i++) {
			if(seq(arr, i, n) == max) ans++;
		}
		return ans;
	}
	static long fact(int n) {
		long ans = 1;
		for(int i = 1; i <= n; i++) ans *= i;
		return ans;
	}
	public static void main(String[] args) throws IOException {
		BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
		/*
		 * char [] s1 = sc.readLine().toCharArray(); char [] s2 =
		 * sc.readLine().toCharArray(); int n1 = 0; int n2 = 0; for(int i = 0; i <
		 * s1.length; i++) { if(s1[i] == '+') n1++; else n2++; } int dn1 = 0; int dn2 =
		 * 0; int q = 0; for(int i = 0; i < s2.length; i++) { if(s2[i] == '+') dn1++;
		 * else if(s2[i] == '-') dn2++; else q++; } if(dn1 + q < n1 || dn2 + q < n2) {
		 * System.out.print(String.format("%.9f", (double)0)); return; } if(q == 0) {
		 * System.out.print(String.format("%.9f", (double)1)); return; } long
		 * totalOutcomes = (long) Math.pow(2, q); int rPlus = 0; int rNeg = 0; if(n1 -
		 * dn1 > 0) rPlus = n1 - dn1; else rNeg = Math.abs(n1 - dn1); if(n2 - dn2 > 0)
		 * rNeg = n2 - dn2; else rPlus = Math.abs(n2 - dn2);
		 * //System.out.println((fact(rNeg + rPlus) / (fact(rNeg) * fact(rPlus))));
		 * double ans = (double) (fact(rNeg + rPlus) / (fact(rNeg) * fact(rPlus))) /
		 * totalOutcomes; System.out.println(String.format("%.9f", ans));
		 */
		int a = Integer.parseInt(sc.readLine());
		for(int t = 0; t < a; t++) {
			long n = Integer.parseInt(sc.readLine());
			int c = 1;
			long x = 0, y = 0;
			long x_y = n - c;
			if(x_y % 2 == 0) {
				x = (x_y / 2) + 1;
				y = x_y - x;
				//System.out.println(c * x + " " + c * y + " " + c);
			}
			else {
				x = x_y / 2;
				y = x_y - x;
				//System.out.println(c * x + " " + c * y + " " + c);
				
			}
			while(gcd(x, y) != 1) {
				x++;
				y--;
			}	
			System.out.println(c * x + " " + c * y + " " + c);
		}
	}
}
