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

from math import *
from functools import *
from time import *
from sys import *
#st = time()
print = stdout.write
#input = __builtins__.input
#input = stdin.readline
def pfactor(n):
    if not n%2:
        return 2
    return 1 
    if pow(2, n-1, n)==n:
        return 1
    #d = {}
    for p in range(2, int(n**0.5)+1):
        if not n%p:
            return p
           # n//=p
       #     if p in d:
       #         d[p]+=1
       #     else:
       #         d[p]=1
        if n==1 or p>int(n**0.5)+5:
            return 1
 #   if n>1:
 #       d[n]=1
 #       n//=n
    return 1
#factor = factorint
def f(n):
    k = pfactor(n)#min(pfactor(n).keys())
  #  print(n, k)
    if k==n:
        k = 1
    for i in range(1, n//k+1):
    #    print(i)
        if k>0 and n-k-i*k>0 and len(set((k, n-k-i*k, i*k)))==3:
            return i*k, (n-k)-i*k, k
@lru_cache(maxsize=None)
def f2(n):
    for a in range(1, n):
        for b in range(1, n):
            if gcd(a, b)+a+b==n and a!=b and a!=gcd(a, b) and b!=gcd(a, b):
                return a,b,gcd(a,b)
a = int(input())
lls = []
for i in range(1, a+1):
    ll = int(input())
    k = f(ll)
    if not k:
        k=f2(ll)
    if not k:
        print(9024)
    lls.append(str(k[0])+' '+str(k[1])+' '+str(k[2]))
lls = '\n'.join(lls)
#for i in lls:
#    print(i)
#    print('\n')
#    pass
print(lls)
#print(str(a))
print('\n')
#print(str(time()-st))
#gcd((n-k)-i*k, i*k)==k