#include <bits/stdc++.h>
#define per(i, a, b) for(int i=a; i<b; i++)
#define rep(i, a, b) for(int i=b-1; i>=a; i--)
using namespace std;
typedef long long ll;

const ll mod(998244353);
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
const int MAXN(2e5+7);

int T, N;
int nm2[40];
int S[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    nm2[0] = 1;
    per(i, 1, 30) {
        nm2[i] = nm2[i-1]*2;
    }
    S[1] = 2;
    per(i, 2, MAXN) {
        per(j, 0, 24) {
            if(!(nm2[j]&i)) {
                S[i] = nm2[j];
                break;
            }
        }
    }
    cin >> T;
    while(T--) {
        cin >> N;
        if(S[N]>N) {
            cout << 1 << '\n';
            per(i, 2, N) {
                cout << S[i] << ' ';
            }
            cout << 1 << '\n';
        } else {
            cout << 0 << '\n';
            per(i, 2, N) {
                cout << S[i] << ' ';
            }
            cout << S[N] << '\n';
        }
    }

    return 0;
}

#include<bits/stdc++.h>
#define FIN freopen("./1007.in","r",stdin)
using namespace std;
int T,matri[4][4],ans;
struct point{
    int x,y;
}p_0,pf;
int main(){
#ifndef ONLINE_JUDGE
    FIN;
#endif
    cin>>T;
    while(T--){
        ans=0;
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                cin>>matri[i][j];
                if(matri[i][j]==0){
                    p_0.x=i,p_0.y=j;
                }
            }
        }
        for(int i=p_0.x+1;i<4;i++){
            swap(matri[p_0.x][p_0.y],matri[i][p_0.y]);
            p_0.x=i;
        }
        for(int i=p_0.y+1;i<4;i++){
            swap(matri[p_0.x][p_0.y],matri[p_0.x][i]);
            p_0.y=i;
        }
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                if(matri[i][j]!=4*i+j+1&&(i!=3||j!=3)){
                    int flag=0;
                    for(int p=0;p<4;p++){
                        for(int q=0;q<4;q++){
                            if(matri[p][q]==4*i+j+1){
                                pf.x=p,pf.y=q;
                                flag=1;
                                break;
                            }
                        }
                        if(flag){
                            break;
                        }
                    }
                    swap(matri[i][j],matri[pf.x][pf.y]);
                    ans++;
                }
            }
        }
        if(ans%2){
            cout<<"No\n";
        }else{
            cout<<"Yes\n";
        }
    }
}

#pragma warning(disable:4996)

#include<bits/stdc++.h>
#define upf(a,b,c) for(ll a=b;a<=c;++a)
#define drf(a,b,c) for(ll a=b;a>=c;--a)
#define ll long long
const int mod(1e9 + 7);
const double esp(1e-6);
const int maxn(1e5 + 5);
using namespace std;
ll T, n, k;
//素数筛选
const int MAXN = 11000;
ll prime[MAXN + 1];//得到小于等于MAXN的所有素数
void getPrime()
{
    memset(prime, 0, sizeof(prime));
    for (ll i = 2; i <= MAXN; i++)
    {
        if (!prime[i])prime[++prime[0]] = i;
        for (ll j = 1; j <= prime[0] && prime[j] * i <= MAXN; j++)      //除法改为乘法提速， 改为除法防止爆范围
        {
            prime[prime[j] * i] = 1;
            if (i % prime[j] == 0)break;
        }
    }
}
int main() {
#ifdef ACM_LOCAL
    freopen("./ACM.in", "r", stdin);
    freopen("./ACM.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    memset(prime, 0, sizeof(prime));
    getPrime();
    cin >> T;
    while (T--) {
        cin >> n;
        ll num = 100;
        ll number;
        upf(i, 1, 1235) {
            number = 0;
            while (n % prime[i] == 0) {
                n /= prime[i];
                number++;
            }
            if (number != 0)
                num = min(number, num);
            if (num == 1)
                break;
        }
        ll tmp2, tmp3, tmp4;
        tmp2 = pow(n, 0.5)+0.5;
        tmp3 = pow(n, 1.0 / 3)+0.5;
        tmp4 = pow(n, 0.25)+0.5;
        if (pow(tmp4, 4) == n && n != 1) {
            if (num > 4)
                num = 4;
        }
        else if (pow(tmp3, 3) == n && n != 1) {
            if (num > 3)
                num = 3;
        }
        else if (pow(tmp2, 2) == n && n != 1) {
            if (num > 2)
                num = 2;
        }
        else if(n!=1){
            num = 1;
        }
        if (num == 100)
            num = 0;
        cout << num << '\n';
    }
}