human
PYTHON3 solution for "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.":
assistant
#Here is Python code to 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.
 def prime_sieve(n):
    """returns a sieve of primes >= 5 and < n"""
    flag = n % 6 == 2
    sieve = bytearray((n // 3 + flag >> 3) + 1)
    for i in range(1, int(n**0.5) // 3 + 1):
        if not (sieve[i >> 3] >> (i & 7)) & 1:
            k = (3 * i + 1) | 1
            for j in range(k * k // 3, n // 3 + flag, 2 * k):
                sieve[j >> 3] |= 1 << (j & 7)
            for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
                sieve[j >> 3] |= 1 << (j & 7)
    return sieve
def prime_list(n):
    """returns a list of primes <= n"""
    res = []
    if n > 1:
        res.append(2)
    if n > 2:
        res.append(3)
    if n > 4:
        sieve = prime_sieve(n + 1)
        res.extend(3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not (sieve[i >> 3] >> (i & 7)) & 1)
    return res
def is_prime(n):
    """returns True if n is prime else False"""
    if n < 5 or n & 1 == 0 or n % 3 == 0:
        return 2 <= n <= 3
    s = ((n - 1) & (1 - n)).bit_length() - 1
    d = n >> s
    for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
        p = pow(a, d, n)
        if p == 1 or p == n - 1 or a % n == 0:
            continue
        for _ in range(s):
            p = (p * p) % n
            if p == n - 1:
                break
        else:
            return False
    return True
arr=prime_list((10**5+2))
t=int(input())
for i in range(t):
    n=int(input())
    if n%2==0:
        a=n//2
        b=a-1
        print(b,a,1)
    else:
        if (n//2)%2==0:
            print((n//2)+1,(n//2)-1,1)
        else:
            print((n//2)-2,(n//2)+2,1)