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

public class Solution {

    /* -------------------------------------- Main Start ----------------------------------- */
    
    private static String s;
    private static boolean found;
    public static void main(String[] args) throws IOException {
        FastReader fs = new FastReader();
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(fs.nextLine());
        while(t-- > 0){
            long n = fs.nextLong();
            for(long i = 2; true; i++){
                if(fs.gcd(i, n - i - 1) != 1) continue;
                System.out.println(i + " " + (n - i - 1) + " 1");
                break;
            }
        } 
    }
    
    
  
    /* ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- 

      StringBuilder sb = new StringBuilder();
      sb.append(x + "\n");
    
      Collections.sort(arr, (a, b) -> Integer.compare(a[0], b[0]))
      arr.toArray(new int[arr.size()][])
      
      List<List<Integer>> pair = new ArrayList<>();
      pair.add(Arrays.asList(nums[i], nums[j],-sum));
    
     */
    private static final int MOD_1 = 1000000000 + 7;

    static class FastReader {

        BufferedReader br;
        StringTokenizer st;

        public FastReader() throws IOException {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        String nextLine() throws IOException {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        /* --------------------------------------------------------------------------------------------------------------------------------------------------------------------- */
        void printArray(int[] arr) {
            System.out.println(Arrays.toString(arr));
        }

        void printArray(String[] arr) {
            System.out.println(Arrays.toString(arr));
        }

        void printArray(long[] arr) {
            System.out.println(Arrays.toString(arr));
        }

        void print(int data) {
            System.out.println(data);
        }

        void print(String data) {
            System.out.println(data);
        }

        void print(long data) {
            System.out.println(data);
        }

        int[] II(int n) throws IOException {
            int[] d = new int[n];
            String[] arr = nextLine().split(" ");
            for (int i = 0; i < n; i++) {
                d[i] = Integer.parseInt(arr[i]);
            }

            return d;
        }

        String[] IS(int n) throws IOException {
            return nextLine().split(" ");
        }

        long[] IL(int n) throws IOException {
            long[] d = new long[n];
            String[] arr = nextLine().split(" ");
            for (int i = 0; i < n; i++) {
                d[i] = Long.parseLong(arr[i]);
            }
            return d;
        }

        public long gcd(long a, long b) {
            if (a == 0) {
                return b;
            }
            return gcd(b % a, a);
        }

        public long power(long x, long y, long p) {
            long res = 1;
            x = x % p;
            if (x == 0) {
                return 0;
            }

            while (y > 0) {
                if ((y & 1) == 1) {
                    res = (res * x) % p;
                }
                y = y >> 1;
                x = (x * x) % p;
            }
            return res;
        }

        void sieveOfEratosthenes(boolean prime[], int size) {
            Arrays.fill(prime, true);
            prime[0] = prime[1] = false;
            prime[2] = true;

            for (int p = 2; p * p < size; p++) {
                if (prime[p] == true) {
                    for (int i = p * p; i < size; i += p) {
                        prime[i] = false;
                    }
                }
            }
        }

        public long fact(long n) {
            long ans = 1;
            for (int i = 2; i <= n; i++) {
                ans = (ans * i) % MOD_1;
            }
            return ans;
        }

        public long lcm(long a, long b) {
            return (a * b) / gcd(a, b);
        }

        public int log2(int N) {
            int result = (int) (Math.log(N) / Math.log(2));
            return result;
        }

        // find first element in the arr that is equal to the x. 
        // If x is not present in arr then it will return first element that is greater than x
        // It return arr.size() if all element are smaller than x
        public int lowerBound(int[] a, int x) {
            int l=-1,r=a.length;
            while(l+1<r) {
              int m=(l+r)>>>1;
              if(a[m]>=x) r=m;
              else l=m;
            }
            return r;
        }

        // find first element in the arr that is greater than x. 
        // It return arr.size() if all element are smaller than x
        public int upperBound(int[] a, int x) {
            int l=-1,r=a.length;
            while(l+1<r) {
               int m=(l+r)>>>1;
               if(a[m]<=x) l=m;
               else r=m;
            }
            return l+1;
        }

    }

}
