#include<bits/stdc++.h>

using namespace std;
mt19937 rnd(114514);
int dist[1000005],last[1000005];
const int tt=2000;
vector<pair<int,int> >zy[tt+5];
vector<int>sav[tt+5];
pair<int,int>val[tt+5];
int f[2][105];
bool check(vector<int>S){
    int sum=0;
    for(auto x:S)sum+=x;
    return sum!=0&&sum!=-1;
}
pair<int,int> calc(vector<int>S){
    memset(f,0,sizeof(f));f[0][50]=1;
    for(auto x:S){
        for(int j=0;j<=100;j++){
            f[1][j]+=f[0][j];
            if(j+x>=0&&j+x<=100)f[1][j+x]+=f[0][j];
        }
        for(int j=0;j<=100;j++)f[0][j]=f[1][j],f[1][j]=0;
    }
    return {f[0][50],f[0][49]};
}
vector<int>ans;
void Solve(int x){
    if(!x)return;
    int u=last[x],la=x-val[u].second;
    // cerr<<val[u].first<<" "<<val[u].second <<" "<<sav[u].size()<<endl;
    if(x==val[u].first){
        ans=sav[u];
        return;
    }
    if(val[u].first)la/=val[u].first;
    Solve(la);
    long long X=0,Y=0;
    for(auto x:ans){
        if(x>0)X+=x;
        else Y+=x;
    }
    long long S=(X>-Y?X:Y);//cerr<<S<<endl;
    for(auto x:sav[u])ans.push_back(x*S);
    // for(auto x:ans)cerr<<x<<" ";cerr<<endl;
}
int main(){
    int fr=0;const int N=1e6;
    for(int i=1;i<=N;i++)dist[i]=31;
    for(int t=1;t<=tt;t++){
        int len=rnd()%12+3;
        vector<int>S;
        S.resize(len);
        for(int i=0;i<len;i++)S[i]=((rnd()&1)?(rnd()%3+1):-(int)(rnd()%3+1));
        while(!check(S))for(int i=0;i<len;i++)S[i]=((rnd()&1)?(rnd()%3+1):-(int)(rnd()%3+1));
        auto [x,y]=calc(S);sav[t]=S;val[t]={x,y};
        zy[x].push_back({y,t});fr=max(fr,x);
        if(len<dist[x])dist[x]=len,last[x]=t;
    }
    for(int i=0;i<=fr;i++)sort(zy[i].begin(),zy[i].end());
    for(int i=1;i<=N;i++){
        if(dist[i]>30){cerr<<i<<endl;break;}
        for(int u=0;u<=fr;u++){
            if(i*u>N)break;
            for(auto [x,y]:zy[u]){
                if(dist[i]+x>N)break;
                int v=i*u+x;
                if(v>N)continue;
                if(dist[v]>dist[i]+sav[y].size())dist[v]=dist[i]+sav[y].size(),last[v]=y;
            }
        }
    }
    int T;
    scanf("%d",&T);
    while(T--){
        int x;
        scanf("%d",&x);ans.clear();
        Solve(x);
        printf("%d\n",(int)ans.size());
        for(auto x:ans)printf("%d ",x);putchar('\n');
    }
    return 0;
}