import math
A = [1]
B = [0]
for n in range(4,62,2):
A.append((B[-1]+math.comb(n-1,n//2-1))%998244353)
B.append((math.comb(n,n//2)-A[-1]-1)%998244353)
t = int(input())
for _ in range(t):
n = int(input())
ind = n//2-1
print(str(A[ind])+" "+str(B[ind])+" "+"1")#include <bits/stdc++.h>
using namespace std;
const int N=70;
const int mod=998244353;
long long c[N][N];
void init(){
c[1][1]=1;
for(int i=1;i<=65;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++){
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
}
void solved(){
int n;
cin>>n;
std::vector<long long > dp(n+1),b(n+1);
dp[2]=1;
b[2]=0;
for(int i=4;i<=n;i+=2){
dp[i]=c[i-2][i/2-2]+c[i-2][(i-2)/2]+b[i-2];
dp[i]%=mod;
b[i]=(c[i][i/2]-dp[i]-1+mod)%mod;
b[i]%=mod;
}
cout<<dp[n]<<" "<<b[n]<<" "<<1<<endl;
}
int main(){
ios::sync_with_stdio(false );
cin.tie(0);
cout.tie(0);
int t;
init();
cin>>t;
while(t--) solved();
}1294C - Product of Three Numbers | 749A - Bachgold Problem |
1486B - Eastern Exhibition | 1363A - Odd Selection |
131B - Opposites Attract | 490C - Hacking Cypher |
158B - Taxi | 41C - Email address |
1373D - Maximum Sum on Even Positions | 1574C - Slay the Dragon |
621A - Wet Shark and Odd and Even | 1395A - Boboniu Likes to Color Balls |
1637C - Andrew and Stones | 1334B - Middle Class |
260C - Balls and Boxes | 1554A - Cherry |
11B - Jumping Jack | 716A - Crazy Computer |
644A - Parliament of Berland | 1657C - Bracket Sequence Deletion |
1657B - XY Sequence | 1009A - Game Shopping |
1657A - Integer Moves | 230B - T-primes |
630A - Again Twenty Five | 1234D - Distinct Characters Queries |
1183A - Nearest Interesting Number | 1009E - Intercity Travelling |
1637B - MEX and Array | 224A - Parallelepiped |