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

//package codeforces;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class solution{
	public static void main(String[] args){
		FastScanner s=new FastScanner();
    	PrintWriter out=new PrintWriter(System.out);
    	int t=s.nextInt();
    	for(int tt=0;tt<t;tt++) {
    		long n=s.nextLong();
    		if((n)%2==0) {
    			out.println(2+" "+(n-3)+" "+1);
    		}else {
    			if((n-4)%3!=0) {
    				out.println(3+" "+(n-4)+" "+1);
    			}else if((n-6)%5!=0){
    				out.println(5+" "+(n-6)+" "+1);
    			}else {
    				out.println(7+" "+(n-8)+" "+1);
    			}
    		}
    		
       	}
    	out.close();
    }
	public static void printb(boolean ans) {
		if(ans) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}
	static boolean isPrime(int n){
        if (n <= 1)
            return false;
        else if (n == 2)
            return true;
        else if (n % 2 == 0)
            return false;
        for (int i = 3; i <= Math.sqrt(n); i += 2){
            if (n % i == 0)
                return false;
        }
        return true;
    }
	static long lcm(long a,long b){
	      return (a*b)/(gcd(a,b));
	    }
	static long gcd(long a, long b){
	      if (b == 0)
	        return a;
	      return gcd(b, a % b);
	    }
    static void sort(long [] a) {
		ArrayList<Long> l=new ArrayList<>();
		for (long i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
    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 FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		boolean nextBoolean() {
			return Boolean.parseBoolean(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		long[] readLongArray(int n) {
			long[] a=new long[n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}
	}
    static class Pair implements Comparable<Pair>{
    	int a,b; 
    	Pair(int a,int b){
    		this.a=a;
    		this.b=b;
    	}
    	public int compareTo(Pair o) {
    		if(b==o.b) {
    			return o.a-a;
    		}
    		return b-o.b;
    	}
    }
}
