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

import java.io.* ;
@SuppressWarnings("unused")
 
public class A
{
	static final int mod = (int)1e9+7 ;
	static final double pi = 3.1415926536 ;
	static boolean not_prime[] = new boolean[10000001] ;
	static void sieve() {
		for(int i=2 ; i*i<10000001 ; i++) {
			if(not_prime[i]==false) {
				for(int j=2*i ; j<10000001 ; j+=i) {
					not_prime[j]=true ;
				}
			}
		}not_prime[0]=true ; not_prime[1]=true ;
	}		
	public static long bexp(long base , long power)
	{
		long res=1L ;
		
		base = base%mod ;
		
		while(power>0) {
			if((power&1)==1) {
				res=(res*base)%mod ;
				power-- ;
			}
			else {
				base=(base*base)%mod ;
				power>>=1 ;
			}
		}
		
		return res ;
	}
	static long modInverse(long n, long p){return power(n, p - 2, p); }
	static long power(long x, long y, long p)
	{
	  
	    // Initialize result
	    long res = 1;
	    x = x % p;
	  
	    while (y > 0) {
	  
	        if (y % 2 == 1)
	            res = (res * x) % p;
	        
	        y = y >> 1;
	        x = (x * x) % p;
	    }
	  
	    return res;
	}
	static long nCrModPFermat(int n, int r, long p){if(n<r) return 0 ;if (r == 0)return 1; long[] fac = new long[n + 1];fac[0] = 1;for (int i = 1; i <= n; i++)fac[i] = fac[i - 1] * i % p;return (fac[n] * modInverse(fac[r], p) % p* modInverse(fac[n - r], p) % p) % p;}	
	static long modular_add(long a, long b){ return ((a % mod) + (b % mod)) % mod; }
	static long modular_sub(long a, long b){ return ((a % mod) - (b % mod) + mod) % mod; }
	static long modular_mult(long a, long b){ return ((a % mod) * (b % mod)) % mod; }	
	static long lcm(long f, long f2){ return (f / gcd(f, f2)) * f2; }
	static long gcd(long a, long b){if (b == 0) {return a;}return gcd(b, a % b);}
	static int cbits(long x) {return (int)(Math.log(x)/Math.log(2)+1) ;}
	
	public static void main(String[] args)throws Exception
    {
		FastReader in = new FastReader() ;
		StringBuilder op = new StringBuilder() ;
		int T = in.nextInt(); 
	//	int T=1 ;
		for(int tt=0 ; tt<T ; tt++){
			
			int n = in.nextInt()-1 ;
			for(int i=2 ; i<=n/2+1 ; i++) {
				int first = i ;
				int second = n-i ;
				if(gcd(first , second) == 1) {
					op.append(first+" "+second+" "+1+"\n") ;
					break ;
				}
			}
		}
		System.out.println(op.toString());
    }
	

	static class pair implements Comparable<pair>
	{
		int first , second ;
		pair(int first , int second){
			this.first=first ;
			this.second=second; 
		}
		public int compareTo(pair other) {
			return this.second-other.second ;
		}
	}
	
	static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
	
	static 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;
        }
        
        int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
    }

}