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 Test {
	public static void main(String[] args) throws IOException, InterruptedException {
	   Scanner sc = new Scanner(System.in);
	   PrintWriter pw = new PrintWriter(System.out);
	   int t = sc.nextInt();
	   while(t-->0) {
		   long n = sc.nextLong();
		  
		   if (n%2==0) {
			   long c = 1;
			   long a = (n%2==0)?(n-c)/2:((n-c)/2)-1;
			   long b = n-a-c;
			   System.out.println(a+" "+b+" "+c);

		   }
		   else if (((n-1)/2)%2 ==0) {
			   long c = 1;
			   long a = ((n-c)/2)-1;
			   long b = n-a-c;
			   System.out.println(a+" "+b+" "+c);

		   }
		   else {
			   long c = 1;
			   long a = ((n-c)/2)-2;
			   long b = n-a-c;
			   System.out.println(a+" "+b+" "+c);

		   }
	  }}
	static long lcm (long a, long b) {
		return a*b /gcd(a, b);
	}
	static Pair extendedEuclid (long a , long b) {
		if (b==0) {
			return new Pair (1,0);
		}
		Pair temp = extendedEuclid(b, a%b);
		return new Pair (temp.y,temp.x-(a/b)*temp.y);
	}
	static ArrayList<Integer> primes;
	static ArrayList <Pair> primeFactors;
	static void primeFactorization(long n) {
		for(int i : primes) {
			int c = 0;
			while(n%i ==0) {
				c++;
				n/=i;
			}
			if(c!=0) {
				primeFactors.add(new Pair(i, c));
			}
		}
		if(n!=1) {
			primeFactors.add(new Pair(n, 1));
		}
	}
	static  void sieveOfEratosthenes(int n)
	    {
	        // Create a boolean array "prime[0..n]" and initialize
	        // all entries it as true. A value in prime[i] will
	        // finally be false if i is Not a prime, else true.
	        boolean prime[] = new boolean[n+1];
	        for(int i=0;i<=n;i++)
	            prime[i] = true;
	         
	        for(int p = 2; p*p <=n; p++)
	        {
	            // If prime[p] is not changed, then it is a prime
	            if(prime[p] == true)
	            {
	            	primes.add(p);
	                // Update all multiples of p
	                for(int i = p*p; i <= n; i += p)
	                    prime[i] = false;
	            }
	        }}
	static void paint (int i,int j,int k) {
		painted[i][j] = true;
		for(int c = 1;c<=k;c++) {
			painted[i-c][j+c]=true;
			painted[i-c][j-c] = true;
		}
	}
	static long gcd1(long a, long b) {
		if(b==0) {
			return a;
		}
		return gcd1 (b, a%b);
	}
	static boolean canMoveDiagonalRight(int i, int j) {
		if (i-1>=0&&j+1<m&&map[i-1][j+1]=='*') {
			return true;
		}
		return false;
	}
	static int longestIncreasingSubsequence (int [] arr) {
		ArrayList<Integer> lcs = new ArrayList<Integer>();
		for(int i = 0;i<arr.length;i++) {
	         int ans = -1;
	         int l = 0;
	         int r = lcs.size()-1;
	         while(l<=r) {
	        	 int mid = (l+r)/2;
	        	 if(arr[lcs.get(mid)]>=arr[i]) {
	        		 ans = mid;
	        		 r = mid -1;
	        	 }
	        	 else {
	        		 l = mid +1;
	        	 }
	         }
	         if(ans ==-1) {
	        	 lcs.add(i);
	         }
	         else {
	        	 lcs.set(ans, i);
	         }
	         for(Integer e: lcs) {
	        	// System.out.print(e+" ");
	        	 
	         }
	        // System.out.println();
		}
		
		return lcs.size();
	}
	static boolean canMoveDiagonalLeft(int i, int j) {
		if (i-1>=0&&j-1>=0&&map[i-1][j-1]=='*') {
			return true;
		}
		return false;
	}
    static int countDiagonal(int start, int end) {
    	int countRight = 0;
    	int countLeft = 0;
    	int i = start;
    	int j = end ;
    	while(canMoveDiagonalRight(i, j)) {
    		countRight++;
    		i = i-1;
    		j = j+1;
    	}
    	i = start;
        j = end ;
    	while(canMoveDiagonalLeft(i, j)) {
    		countLeft++;
    		i = i-1;
    		j = j-1;
    	}
    	return Math.min(countLeft, countRight);
    }
    static boolean [][] painted;
	static char [][]map ;
	//static int k;
	static long cost (int k ) {
		Long [] costs = new Long[n];
		for(int i = 0;i<n;i++) {
			costs [i] = arr[i]*1l + (i+1)*k*1l;
			
		}
		long ans = 0;
		Arrays.sort(costs);
		for(int i  = 0;i<k;i++) {
			ans += costs[i];
		}
		return ans;
	}
	static long [] a;
	static long [] b;
	static int k;
	//static  HashMap< String, Boolean> map;
	static  long [] arr;
	static LinkedList<Integer> first;
	static LinkedList<Integer> second;
	
	static Pair [] islands;
    static HashSet<Integer> special ;
    
	

    	
    	
    
    static ArrayList <StringBuilder> ans ;
    
   
    static int mod=1000000007;  
    static int n;
    static int m;
    static int [][][]dp;
	static int bitCount (int msk) {
		int comp = 1;
		int count = 0;
		while(comp<=msk) {
			if((msk&comp)!=0) {
				count++;
			}
			comp = comp<<1;
		}
		return count;
	}

		   static class triple {
	            int u;
	            int v;
	            int z;
	 
	            public triple(int u, int v, int z) {
	                this.u = u;
	                this.v = v;
	                this.z = z;
	            }
	 
	            public String toString() {
	                return "triple{" +
	                        "u=" + u +
	                        ", v=" + v +
	                        ", z=" + z +
	                        '}';
	            }
	 
	            public boolean equals(Object o) {
	                if (this == o) return true;
	                if (o == null || getClass() != o.getClass()) return false;
	                triple triple = (triple) o;
	                return u == triple.u &&
	                        v == triple.v &&
	                        z == triple.z;
	            }
	 
	            public int hashCode() {
	                return Objects.hash(u, v, z);
	            }}
	 
 
			
 
 
 
	static class Pair  {
		public long x;
		public long y;
		public Pair (long x, long y) {
			this.x = x;
			this.y = y;
			
		}
		public double distance( Pair p) {
			return Math.sqrt((y-p.y)*(y-p.y)+(x-p.x)*(x-p.x));
		}
		@Override
		public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair triple = (Pair) o;
            return x == triple.x &&
                    y == triple.y ;
                
        }
		
		
	}static long modPow(long a, long x, long p) {
	    //calculates a^x mod p in logarithmic time.
	    long res = 1;
	    while(x > 0) {
	        if( x % 2 != 0) {
	            res = (res * a) % p;
	        }
	        a = (a * a) % p;
	        x /= 2;
	    }
	    return res;
	}
 
	static long modInverse(long a, long p) {
	    //calculates the modular multiplicative of a mod m.
	    //(assuming p is prime).
	    return modPow(a, p-2, p);
	}
	static long [] fact;
	static long nCr1(int n, int r,long mod)
	{ //System.out.println(r);
	   long numerator = fact[n]%mod;
	  // System.out.println(r+" "+(n-r));
	   long deno = ((fact[r]%mod)*(fact[n-r]%mod))%mod;
	
	    return (numerator*modInverse(deno,mod))%mod;
	}
 
	static ArrayList <Integer> prime;
	 static void simpleSieve(int limit)
	    {   
	        // Create a boolean array "mark[0..n-1]" and initialize
	        // all entries of it as true. A value in mark[p] will
	        // finally be false if 'p' is Not a prime, else true.
	        boolean mark[] = new boolean[limit+1];
	         
	        for (int i = 0; i < mark.length; i++)
	            mark[i] = true;
	      
	        for (int p=2; p*p<limit; p++)
	        {
	            // If p is not changed, then it is a prime
	            if (mark[p] == true)
	            {
	                // Update all multiples of p
	                for (int i=p*p; i<limit; i+=p)
	                    mark[i] = false;
	            }
	        }
	      
	        // Print all prime numbers and store them in prime
	        for (int p=2; p<limit; p++)
	        {
	            if (mark[p] == true)
	            {
	                prime.add(p);
	               // System.out.print(p + "  ");
	            }
	        }
	    }
 
	 
	 public static long gcd (long a, long b ) {
		 if(b==0) {
			 return a;
		 }
		 else {
			 return gcd1 (b, a%b);
		 }
	 }
	 
 static class Scanner {
 		StringTokenizer st;
 		BufferedReader br;
  
 		public Scanner(InputStream s) {
 			br = new BufferedReader(new InputStreamReader(s));
 		}
        public Scanner(FileReader r) {
        	br = new BufferedReader(r);
        }
 		public boolean hasNext() {
 			// TODO Auto-generated method stub
 			return false;
 		}
  
 		public String next() throws IOException {
 			while (st == null || !st.hasMoreTokens())
 				st = new StringTokenizer(br.readLine());
 			return st.nextToken();
 		}
  
 		public int nextInt() throws IOException {
 			return Integer.parseInt(next());
 		}
  
 		public long nextLong() throws IOException {
 			return Long.parseLong(next());
 		}
  
 		public String nextLine() throws IOException {
 			return br.readLine();
 		}
  
 		public double nextDouble() throws IOException {
 			String x = next();
 			StringBuilder sb = new StringBuilder("0");
 			double res = 0, f = 1;
 			boolean dec = false, neg = false;
 			int start = 0;
 			if (x.charAt(0) == '-') {
 				neg = true;
 				start++;
 			}
 			for (int i = start; i < x.length(); i++)
 				if (x.charAt(i) == '.') {
 					res = Long.parseLong(sb.toString());
 					sb = new StringBuilder("0");
 					dec = true;
 				} else {
 					sb.append(x.charAt(i));
 					if (dec)
 						f *= 10;
 				}
 			res += Long.parseLong(sb.toString()) / f;
 			return res * (neg ? -1 : 1);
 		}
  
 		public boolean ready() throws IOException {
 			return br.ready();
 		}
  
 	}
}