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

public class A2 {

    void solve() {
        long n = clong();
        for (long b = 2; b < n; b++) {
            for (long c = 1; c < b; c++) {
                long a = n - b - c;
                if (a > b && gcd(a, b) == c) {
                    cout(a + " " + b + " " + c);
                    return;
                }
            }
        }
    }

    long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    static int[] primes(int n) {
        BitSet np = new BitSet(n + 1); // not prime
        int size = 0;
        for (int i = 2; i <= n; i++) {
            if (!np.get(i)) {
                size++;
                for (long j = i * (long)i; j <= n; j += i) {
                    np.set((int)j);
                }
            }
        }
        int[] res = new int[size];
        for (int i = 2, j = 0; i <= n; i++) {
            if (!np.get(i)) {
                res[j++] = i;
            }
        }
        return res;
    }

    static BitSet primeSet(int n) {
        BitSet p = new BitSet(n + 1);
        p.flip(2, n + 1);
        for (int i = 2; i <= n; i++) {
            if (p.get(i)) {
                for (long j = i * (long)i; j <= n; j += i) {
                    p.clear((int)j);
                }
            }
        }
        return p;
    }

    public static void main(String... args) {
        int t = in.nextInt();
        for (int test = 0; test < t; test++) {
            new A2().solve();
        }
        out.flush();
    }

    static final QuickReader in = new QuickReader(System.in);
    static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out, 131_072));

    static int cint() {
        return in.nextInt();
    }

    static long clong() {
        return in.nextLong();
    }

    static String cstr() {
        return in.nextLine();
    }

    static int[] carr_int(int n) {
        return in.nextInts(n);
    }

    static long[] carr_long(int n) {
        return in.nextLongs(n);
    }

    static void cout(int... a) {
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                buf.append(' ');
            }
            buf.append(a[i]);
        }
        out.println(buf);
    }

    static void cout(long... a) {
        StringBuilder buf = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            if (i != 0) {
                buf.append(' ');
            }
            buf.append(a[i]);
        }
        out.println(buf);
    }

    static void cout(Object o) {
        out.println(o);
    }

    static class QuickReader {
        BufferedReader in;
        StringTokenizer token;

        public QuickReader(InputStream ins) {
            in = new BufferedReader(new InputStreamReader(ins));
            token = new StringTokenizer("");
        }

        public boolean hasNext() {
            while (!token.hasMoreTokens()) {
                try {
                    String s = in.readLine();
                    if (s == null) {
                        return false;
                    }
                    token = new StringTokenizer(s);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return true;
        }

        public String next() {
            hasNext();
            return token.nextToken();
        }

        public String nextLine() {
            try {
                String s = in.readLine();
                token = new StringTokenizer("");
                return s;
            } catch (IOException e) {
                throw new InputMismatchException();
            }
        }

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

        public int[] nextInts(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextInt();
            }
            return res;
        }

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

        public long[] nextLongs(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) {
                res[i] = nextLong();
            }
            return res;
        }
    }
}
