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 AiseHi {
	static Scanner sc = new Scanner(System.in);
	static int mod = (int)(1e9+7);
	static Set<Integer> dp[][][];
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		z : while(t-->0) {
			long n = sc.nextLong();
			long cdsdccdsdcsdsxzzxcz = n-3;
			if(cdsdccdsdcsdsxzzxcz%2 == 0) {
				cdsdccdsdcsdsxzzxcz = n - 4;
				System.out.println(3+" "+cdsdccdsdcsdsxzzxcz+" "+1);
			}
			else{
				System.out.println(2+" "+cdsdccdsdcsdsxzzxcz+" "+1);
			}
		}
	}
	private static boolean isPos(List<long[]> val, long mid) {
		for(int i=0;i<val.size();i++) {
			for(int j=0;j<val.get(i).length-1;j++) {
				if(val.get(i)[j]>=mid) return false;
				mid = mid + 1;
			}
		}
		return true;
	}
	static long fac[] = new long[100006];
	
	static void precompute() {
		int n = 100005;
		fac[0] = 1;
		for(int i=1;i<=n;i++)
			fac[i] = (i * fac[i-1])%mod;
	}
	
	static long power(long base, long p, long mod2) {
		
		long ans = 1;
		while(p!=0) {
			if(p%2==0) {
				base = (base*base)%mod2;
				p/=2;
			}
			else {
				ans = (ans*base)%mod2;
				p-=1;
			}
		}
		return (int) (ans%mod2);
	}
	private static boolean checkl(char[] s, char t[]) {
		int i=0, j =0;
		while(i<s.length && j<t.length) {
			if(s[i] == t[j]) {
				j++;
			}
			i++;
		}
		return j==t.length;
	}
	static int gcd(long a,long b) { if(b==0) return (int) a; return gcd(b,a%b); } 
	private static int findn(int[] a, int l, int h, long m) {
		int ret = -1;
		while(l<=h) {
			int mid = (l+h)/2;
			if(a[mid]>m) {
				h = mid-1;
			}
			else {
				ret = mid;
				l = mid+1;
			}
		}
		return ret;
	}
	private static int find(int[] a, int l, int h, long m) {
		int ret = -1;
		while(l<=h) {
			int mid = (l+h)/2;
			if(a[mid]>=m) {
				ret = mid;
				h = mid-1;
			}
			else l = mid+1;
		}
		return ret;
	}
	private static boolean find(String ini, String a) {
		return !KMPSearch(ini,a);
	}
	static boolean KMPSearch(String pat, String txt)
    {
        int M = pat.length();
        int N = txt.length();
 
        int lps[] = new int[M];
        int j = 0; 
        
        computeLPSArray(pat, M, lps);
  
        int i = 0; 
        while (i < N) {
            if (pat.charAt(j) == txt.charAt(i)) {
                j++;
                i++;
            }
            if (j == M) {
                j = lps[j - 1];
                return true;
            }
            else if (i < N && pat.charAt(j) != txt.charAt(i)) {
                if (j != 0)
                    j = lps[j - 1];
                else
                    i = i + 1;
            }
        }
        return false;
    }
  
    static void computeLPSArray(String pat, int M, int lps[])
    {
        int len = 0;
        int i = 1;
        lps[0] = 0; // lps[0] is always 0
  
        // the loop calculates lps[i] for i = 1 to M-1
        while (i < M) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            }
            else // (pat[i] != pat[len])
            {
                // This is tricky. Consider the example.
                // AAACAAAA and i = 7. The idea is similar
                // to search step.
                if (len != 0) {
                    len = lps[len - 1];
  
                    // Also, note that we do not increment
                    // i here
                }
                else // if (len == 0)
                {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }
//	private static boolean check(long n,long val) {
//		if(n == 0) return true;
//		
//		while(val<=n) {
////			if(check(n-val,))
//		}
//	}
	private static int find(int[] a, TreeMap<Integer, Integer> ts, int lp) {
		int ret = 1;
		int idx = -1;
		for(int i=a.length-1;i>=0;i--) {
			if(a[i] == lp) {
				idx = i;
				break;
			}
		}
		idx--;
		int prev = lp;
		while(idx>=0) {
			if((prev - a[idx]) >= lp) {
				ret++;
				prev = a[idx];
			}
			idx--;
		}
		return ret;
	}
	private static void reverse(char[] s) {
		char a[] = new char[s.length];
		for(int i=0;i<s.length;i++) a[i] = s[i];
		for(int i=0;i<s.length;i++)
			s[i] = a[a.length-1-i];
	}
	private static boolean isPalindrome(char[] s) {
		int n = s.length;
		for(int i=0;i<n/2;i++)
			if(s[i]!=s[n-1-i]) return false;
		return true;
	}
	private static boolean is(char[] s) {
		for(char c : s) if(c == '0') return false;
		return true;
	}
//	static int ceil(int a,int b) {
//		return a/b + (a%b==0?0:1);
//	}
	static boolean prime[] = new boolean[2000009];
//	static int fac[] = new int[2000009];
	
	static void sieve() {
		prime[0] = true;
		prime[1] = true;
		int max = 1000000;
		for(int i=2;i*i<=max;i++) {
			if(!prime[i]) {
				for(int j=i*i;j<=max;j+=i) {
					prime[j] = true;
//					fac[j] = i;
				}
			}
		}
	}
//	static long gcd(long a,long b) { if(b==0) return a; return gcd(b,a%b); }
}
 
class DSU {
	int par[];
	int size[];
	DSU(int n) {
		par = new int[n];
		size = new int[n];
		Arrays.fill(size, 1);
		for(int i=0;i<n;i++) par[i] = i;
	}
	int findPar(int x) {
		if(x == par[x]) return x;
		
		return par[x] = findPar(par[x]);
	}
	boolean join(int u,int v) {
		int fu = findPar(u);
		int fv = findPar(v);
		if(fu!=fv) {
			if(size[fu]>size[fv]) {
				par[fv] = fu;
				size[fu] += size[fv];
			}
			else {
				par[fu] = fv;
				size[fv] += size[fu];
			}
			return true;
		}
		else return false;
	}
}

class pair{
	long val;
	char c;
	pair(long val, char c){
		this.val = val;
		this.c = c;
	}
}