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

// cyan go go go!!!
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;
#define RESPA_GOLD ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define popcnt __builtin_popcount
#define all(a) a.begin(),a.end()
#define low_b lower_bound
#define up_b upper_bound
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define mii map<int,int>
#define pll pair<ll,ll>
#define mll map<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define endl '\n'
#define Y second
#define X first
typedef long double ld;
typedef long long ll;
const ll dx[4]={1,-1,0,0};
const ll dy[4]={0,0,1,-1};
const ll mod=1e9+7;
const ll inf=1e18;
const ll N=3e5;
const ll col=107;
void fre_open(){freopen("file.in","r",stdin);freopen("file.out","w",stdout);}
ll binpow(ll n,ll k){if(k==0)return 1ll;if(k%2)return binpow(n,k-1)*n;ll kk=binpow(n,k/2);return kk*kk;}
void solve(){
    ll n;
    cin>>n;
    --n;
    if(__gcd(n-3,3ll)==1){
    cout<<3<<' '<<n-3<<' '<<1<<endl;
    return;
    }
    if(n%2!=0){
        cout<<n/2<<' '<<n-(n/2)<<' '<<1<<endl;
        return;
    }
    cout<<n/2-1<<' '<<n/2+1<<' '<<1<<endl;
}
int main() {
    //fre_open();
    RESPA_GOLD;
    ll tt=1;
    cin>>tt;
    while(tt--) solve();
}
