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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.*;

public class Mainnn {

    // static final File ip = new File("input.txt");
    // static final File op = new File("output.txt");
    // static {
    //     try {
    //         System.setOut(new PrintStream(op));
    //         System.setIn(new FileInputStream(ip));
    //     } catch (Exception e) {
    //     }

    //     // in = new InputReader(System.in);
    // }

    private static final PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        MyScanner sc = new MyScanner();
        // out = new PrintWriter(new BufferedOutputStream(System.out));

        // out.println(result); // print via PrintWriter
        /////////////////////////////////////////////
        int test = 1;
        test = sc.nextInt();
        while (test-- > 0) {
            long n = sc.nextLong();
            if (n % 2 == 0)
                out.println((n - 3) + " " + (2) + " " + (1));
            else {
                long a = n / 2 + 1;
                long b = n / 2 - 1;
                if (a % 2 == 0) {
                    a++;
                    b--;
                }
                long c = 1;
                out.println(a + " " + b + " " + c);
            }
        }
        ///////////////////////////////////////
        out.close();

    }

    static 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) != 0)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    static void sortI(int[] arr) {
        int n = arr.length;
        Random rnd = new Random();
        for (int i = 0; i < n; ++i) {
            int tmp = arr[i];
            int randomPos = i + rnd.nextInt(n - i);
            arr[i] = arr[randomPos];
            arr[randomPos] = tmp;
        }
        Arrays.sort(arr);
    }

    static void sortL(long[] arr) {
        int n = arr.length;
        Random rnd = new Random();
        for (int i = 0; i < n; ++i) {
            long tmp = arr[i];
            int randomPos = i + rnd.nextInt(n - i);
            arr[i] = arr[randomPos];
            arr[randomPos] = tmp;
        }
        Arrays.sort(arr);
    }

    private static long gcd(long a, long b) {
        return (a == 0 ? b : gcd(b % a, a));
    }

    static class pair {
        int a;
        int b;

        pair(int x, int y) {
            this.a = x;
            this.b = y;
        }

        // public int compare(pair p1, pair p2) {
        // if (p1.a > p2.a)
        // return 1;
        // else if (p1.a < p2.a)
        // return -1;
        // return 0;
        // }
    }

    static class first implements Comparator<pair> {

        public int compare(pair p1, pair p2) {
            if (p1.a > p2.a)
                return -1;
            else if (p1.a < p2.a)
                return 1;
            return 0;
        }
    }

    static class second implements Comparator<pair> {

        public int compare(pair p1, pair p2) {
            if (p1.b > p2.b)
                return 1;
            else if (p1.b < p2.b)
                return -1;
            return 0;
        }
    }

    // -----------PrintWriter for faster output---------------------------------

    // -----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            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;
        }

    }
    // --------------------------------------------------------
}