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

# template begins
#####################################
 
# import libraries for input/ output handling
# on generic level
import atexit, io, sys, math, heapq, collections

#input handling
#input of single integer
def get_int(): return int(sys.stdin.readline().strip())
#input of multiple integers
def get_ints(): return map(int, sys.stdin.readline().strip().split())
#input of list
def get_list(): return list(map(int, sys.stdin.readline().strip().split()))
#input of string
def get_string(): return sys.stdin.readline().strip()

#output handling
#writing int output
def write_int(a): sys.stdout.write(str(a)+"\n")
#writing String
def write_str(a): sys.stdout.write(a+"\n")
#writing Array
def write_list(arr): sys.stdout.write(" ".join(map(str, arr)) + "\n")

#general functions
#swap
def swap(arr, a, b):
    arr[a]^=arr[b]
    arr[b]^=arr[a]
    arr[a]^=arr[b]

#NumberOfDigits
def int_len(a): return math.floor(math.log(a,10))+1

#Powerof2
def isPowerOfTwo(x): return x and (not(x & (x-1)))

#Sieve
def Sieve(n):
    prime = [True for i in range(n+1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    res = []
    for i in range(2,len(prime)):
        if (prime[i]):
            res.append(i)
    return res

#binarySearch
def binarySearch (arr, l, r, x):
    if r >= l:
  
        mid = l + (r - l) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binarySearch(arr, l, mid-1, x)
        else:
            return binarySearch(arr, mid + 1, r, x)
    else:
        return -1
def search(arr,x): return binarySearch(arr,0,len(arr)-1,x)

#Array to String
def toString(A): return''.join(A)

# String to array
def toArray(str): return str.split()

#ArraySum
def arrSum(Arr):
    Sum =0
    for i in range (len(Arr)):
        Sum+=Arr[i]
    return Sum

def computeXOR(n) :
 
    # Modulus operator are expensive
    # on most of the computers. n & 3
    # will be equivalent to n % 4.
 
    # if n is multiple of 4
    if n % 4 == 0 :
        return n
 
    # If n % 4 gives remainder 1
    if n % 4 == 1 :
        return 1
 
    # If n%4 gives remainder 2
    if n % 4 == 2 :
        return n + 1
 
    # If n%4 gives remainder 3
    return 0
 

def find_gcd(x, y):
     
    while(y):
        x, y = y, x % y
     
    return x
         
    


#####################################
# template ends

# Code begins
#####################################




N = get_int()
while N >0:
    n = get_int()
    if (n%2==0):
        print(2,n-3,1)
    else:
        A=n-1
        B=A//2
        C=B
        if (B%2==1):
            B-=2
            C+=2
        else:
            B-=1
            C+=1
        print(B,C,1)




    N-=1


#####################################
# Code ends


# Creating 2D array sol = [[0 for i in range(N)] for j in range(N)]