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

#!/bin/python3

import sys
import math

input = sys.stdin.readline

MAX = sys.maxsize
MIN = -sys.maxsize - 1

# UTILITIES

def inp():
    return int(input())

def inpl():
    return list(map(int, input().split()))

def inpstr():
    return list(map(str, input().split()))

def inpstrl():
    res = []
    for c in str(input()):
        res.append(c)
    res.pop(-1)
    return res

def findMaxCrossingSubarray(arr, low, mid, high):
    sum = 0
    leftSum = MIN
    rightSum = MIN

    i = mid
    while i >= low:
        sum += arr[i]
        if sum > leftSum:
            leftSum = sum
            maxLeft = i
        i -= 1

    sum = 0
    j = mid + 1
    while j <= high:
        sum += arr[j]
        if sum > rightSum:
            rightSum = sum
            maxRight = j
        j += 1

    return maxLeft, maxRight, leftSum + rightSum

def findMaxSubarray(arr, low, high):
    if high == low:
        return low, high, arr[low]
    else:
        mid = math.floor((low + high) / 2)

        leftLow, leftHigh, leftSum = findMaxSubarray(arr, low, mid)
        rightLow, rightHigh, rightSum = findMaxSubarray(arr, mid + 1, high)
        crossLow, crossHigh, crossSum = findMaxCrossingSubarray(arr, low, mid, high)

        if leftSum >= rightSum and leftSum >= crossSum:
            return leftLow, leftHigh, leftSum
        elif rightSum >= leftSum and rightSum >= crossSum:
            return rightLow, rightHigh, rightSum
        else:
            return crossLow, crossHigh, crossSum

def binarySearch(x, mid, arr, n):
    if x == arr[mid - 1] or (x > arr[mid - 2] and x < arr[mid - 1]) or (mid == 1 and x < arr[mid - 1]):
        return mid
    elif x > arr[mid - 1]:
        return binarySearch(x, mid + math.ceil((n - mid) / 2), arr, n)
    else:
        return binarySearch(x, mid - math.ceil(mid / 2), arr, mid)

def gcd(a, b):
    if (b == 0):
        return a
    else:
         return gcd(b, a % b)
         
# SOLUTION

def solve(n):
    a = 0
    b = 0
    c = 1

    r = 0

    dif = n - c

    if dif % 2 != 0:
        r = 1
    
    hdif = int(dif / 2)

    if hdif % 2 == 0 and r == 1:
        a = hdif
        b = a + 1
    elif hdif % 2 == 0 and r == 0:
        a = hdif + 1
        b = hdif - 1
    elif hdif % 2 != 0 and r == 1:
        a = hdif
        b = a + 1
    elif hdif % 2 != 0 and r == 0:
        a = hdif - 2
        b = hdif + 2

    res = []
    res.append(a)
    res.append(b)
    res.append(c)

    return res

if __name__ == "__main__":
    res = []
    iter = inp()
    i = 0
    while i < iter:
        n = inp()
        result = solve(n)
        res.append(result)
        i += 1

    for r in res:
        print(*r)
