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.*;
	import java.math.*;
	
	    public class Main {
	
	        // -- static variables --- //
	        static FastReader sc = new FastReader();
	        static PrintWriter out = new PrintWriter(System.out);
	        static int mod = (int) 1000000007;
	        public static void main(String[] args) throws Exception {
	         
	            int t=sc.nextInt();
	            while(t-->0)
	            Main.go();
	//             out.println();
	            out.flush();
	        }
	
	        // >>>>>>>>>>>>>>>>>>> Code Starts <<<<<<<<<<<<<<<<<<<< //
	        static class pair{
	            int  x;int y;
	            pair(int  x,int y){
	                this.x=x;
	                this.y=y;
	            }
							@Override
							public int hashCode() {
								final int prime = 31;
								int result = 1;
								result = prime * result + x;
								result = prime * result + y;
								return result;
							}
							@Override
							public boolean equals(Object obj) {
								if (this == obj)
									return true;
								if (obj == null)
									return false;
								if (getClass() != obj.getClass())
									return false;
								pair other = (pair) obj;
								if (x != other.x)
									return false;
								if (y != other.y)
									return false;
								return true;
							}
	            
	        }


	        static void go() throws Exception {
	        	
	        	int n=sc.nextInt();
	        	if(n%2==0) {
	        		n--;
	        		out.println((n/2+1)+" "+(n/2)+" "+1);
	        	}else {
	        		if((n-6)%5!=0)
	        			out.println(5+" "+(n-6)+" "+1);
	        		else {
	        			n--;
	        			for(int i=3;i<=Math.min(n,1000);i+=2) {
	        				if((n-i)%i!=0) {
	        					out.println(i+" "+(n-i)+" "+1);
	        					return;
	        				}
	        			}
	        		}
	        		
	        	}
	        	
	        	
	        	
	        	
	        	
	        	
	        	
	        }
	        static long lcm(long a,long b) {
	        	return a*b/gcd(a,b);
	        }
	     
	    
	        // >>>>>>>>>>> Code Ends <<<<<<<<< //
	
	        // --For Rounding--//
	        static double round(double value, int places) {
	
	            if (places < 0)
	                throw new IllegalArgumentException();
	            BigDecimal bd = new BigDecimal(Double.toString(value));
	            bd = bd.setScale(places, RoundingMode.HALF_UP);
	            return bd.doubleValue();
	        }
	
	        // ----Greatest Common Divisor-----//
	        static long gcd(long a, long b) {
	            if (b == 0) {
	                return a;
	            }
	            return gcd(b, a % b);
	        }
	
	        // --- permutations and Combinations ---//
	        static long fact[];
	        static long invfact[];
	
	        static long ncr(int n, int k) {
	            if (k < 0 || k > n) {
	                return 0;
	            }
	            long x = fact[n];
	            long y = fact[k];
	            long yy = fact[n - k];
	            long ans = (x / y);
	            ans = (ans / yy);
	            return ans;
	        }
	
	        // ---sieve---//
	        static int prime[] = new int[1000006];
	
	        // static void sieve() {
	        //     Arrays.fill(prime, 1);
	        //     prime[0] = 0;
	        //     prime[1] = 0;
	        //     for (int i = 2; i * i <= 1000005; i++) {
	        //         if (prime[i] == 1)
	        //             for (int j = i * i; j <= 1000005; j += i) {
	        //                 prime[j] = 0;
	        //             }
	        //     }
	        // }
	
	        // ---- Manual sort ------//
	        static void sort(long[] a) {
	            ArrayList<Long> aa = new ArrayList<>();
	            for (long i : a) {
	                aa.add(i);
	            }
	            Collections.sort(aa);
	            for (int i = 0; i < a.length; i++)
	                a[i] = aa.get(i);
	        }
	
	
	        static void sort(int[] a) {
	            ArrayList<Integer> aa = new ArrayList<>();
	            for (int i : a) {
	                aa.add(i);
	            }
	            Collections.sort(aa);
	            for (int i = 0; i < a.length; i++)
	                a[i] = aa.get(i);
	        }
	
	        // --- Fast exponentiation ---//
	        static long pow(long x, long y) {
	            long res = 1l;
	            while (y != 0) {
	                if (y % 2 == 1) {
	                    res = (x * res)%mod;
	                }
	                y /= 2;
	                x = (x * x)%mod;
	            }
	            return res;
	        }
	
	        // >>>>>>>>>>>>>>> Fast IO <<<<<<<<<<<<<< //
	        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());
	            }
	
	            int[] intArray(int n) {
	                int a[] = new int[n];
	                for (int i = 0; i < n; i++)
	                    a[i] = sc.nextInt();
	                return a;
	            }
	
	            long[] longArray(int n) {
	                long a[] = new long[n];
	                for (int i = 0; i < n; i++)
	                    a[i] = sc.nextLong();
	                return a;
	            }
	
	            String nextLine() {
	                String str = "";
	                try {
	                    str = br.readLine();
	                } catch (IOException e) {
	                    e.printStackTrace();
	                }
	                return str;
	            }
	        }
	    }