Problem: Gildong is developing a game consisting of n stages numbered from 1 to n. The player starts the game from the 1-st stage and should beat the stages in increasing order of the stage number. The player wins the game after beating the n-th stage.

There is at most one checkpoint on each stage, and there is always a checkpoint on the 1-st stage. At the beginning of the game, only the checkpoint on the 1-st stage is activated, and all other checkpoints are deactivated. When the player gets to the i-th stage that has a checkpoint, that checkpoint is activated.

For each try of a stage, the player can either beat the stage or fail the stage. If they beat the i-th stage, the player is moved to the i+1-st stage. If they fail the i-th stage, the player is moved to the most recent checkpoint they activated, and they have to beat the stages after that checkpoint again.

For example, assume that n = 4 and the checkpoints are on the 1-st and 3-rd stages. The player starts at the 1-st stage. If they fail on the 1-st stage, they need to retry the 1-st stage because the checkpoint on the 1-st stage is the most recent checkpoint they activated. If the player beats the 1-st stage, they're moved to the 2-nd stage. If they fail it, they're sent back to the 1-st stage again. If they beat both the 1-st stage and the 2-nd stage, they get to the 3-rd stage and the checkpoint on the 3-rd stage is activated. Now whenever they fail on the 3-rd stage, or the 4-th stage after beating the 3-rd stage, they're sent back to the 3-rd stage. If they beat both the 3-rd stage and the 4-th stage, they win the game.

Gildong is going to build the stages to have equal difficulty. He wants you to find any series of stages and checkpoints using at most 2000 stages, where the [expected number](https://en.wikipedia.org/wiki/Expected_value) of tries over all stages is exactly k, for a player whose probability of beating each stage is exactly \cfrac{1}{2}.

Input

Each test contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 50).

Each test case contains exactly one line. The line consists of a single integer k (1 ≤ k ≤ 10^{18}) — the expected number of tries over all stages Gildong wants to set for a player whose probability of beating each stage is exactly \cfrac{1}{2}.

Output

For each test case, print -1 if it's impossible to construct such a series of stages and checkpoints using at most 2000 stages.

Otherwise, print two lines. The first line should contain a single integer n (1 ≤ n ≤ 2000) – the number of stages. The second line should contain n integers, where the i-th integer represents whether the i-th stage has a checkpoint. The i-th integer should be 0 if the i-th stage doesn't have a checkpoint, and 1 if it has a checkpoint. Note that the first integer must be 1 according to the description.

Example

Input


4
1
2
8
12


Output


-1
1
1
4
1 1 1 1
5
1 1 0 1 1

Note

In the first and the second case, we can see that the 'easiest' series of stages is to have 1 stage with a checkpoint. This already requires 2 tries in expectation, so it is impossible to make it to require only 1 try.

In the third case, it takes 2 tries in expectation to beat each stage, and the player can always retry that stage without falling back to one of the previous stages if they fail it. Therefore the total expected number of tries is 8. Note that there exists an answer with fewer stages, but you are not required to minimize the number of stages used. 

Solution (in CPP):

Solution:
#include<bits/stdc++.h>

using namespace std;

#define iOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
//#define mp make_pair
#define L(x) x.length()
#define B(x) x.begin()
#define E(x) x.end()
#define F(x) x.front()
#define SZ(x) x.size()
#define CLR(x) x.clear()
#define SORT(x) sort(x.begin(),x.end())
#define REV(x) reverse(x.begin(),x.end())
#define FOR(i,x,y) for(int i=x;i<y;i++)
#define S(x) scanf("%d",&x)
#define SL(x) cin>>x
#define SD(x) scanf("%lf",&x)
#define SC(x) scanf("%1s",&x)
#define SS(x) scanf("%s",x)
#define DUM() scanf("%c",&dum)
#define READ(x) freopen(x,"r",stdin)
#define WRITE(x) freopen(x,"w",stdout)
#define FILL(x,y) memset(x,y,sizeof(x))
#define IT iterator
//#define ld long double

using namespace std;
typedef long long int lli;
typedef long double ld;
typedef unsigned long long int llu;
typedef pair<int,int> P;
typedef vector<int> VI;
typedef vector< VI > VVI;
typedef vector< P > VP;
typedef vector< VP > VVP;
typedef vector<string> VS;
typedef vector< VS> VVS;
typedef map<int,int> MAP;
//const int big=1e7+5;
/*lli gcd(lli a,lli b)
{
    if(b==0)
        return a;
    ans+=a/b;
    return gcd(b,a%b);
}*/
/*
void minDivsieve()
{
    for(long long int i=0;i<=big;++i)
        arr[i]=i;
    for(long long int i=2;i<=big;++i)
    {
        if(arr[i]!=i)
            continue;
        for(long long int j=i;j<=big;j+=i)
            arr[j]=min(arr[j],i);
    }
}*/

/*long long int fac[1000001];

long long int power(long long int x, long long int y,long long int p)
{
    long long int res = 1; // Initialize result

    x = x % p; // Update x if it is more than or
    // equal to p

    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}

// Returns n^(-1) mod p
long long int modInverse(long long int n, int p)
{
    return power(n, p - 2, p);
}

// Returns nCr % p using Fermat's little
// theorem.
long long int nCrModPFermat(unsigned long long n,
                                 long long int r, long long int p)
{
    // Base case
    if (r == 0)
        return 1;

    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}


*/
//const int mod=1e9+7;

/*vector<vector<int> >v(100005);
int num[100005];
bool visited[100005];

int dfs(int node)
{
    visited[node]=true;
    //cout<<"size of node "<<node<<": "<<v[node].size()<<endl;
    if(v[node].size()==1)
    {
        if(visited[v[node][0]])
        {
            num[node]=1;
            //cout<<node<<": "<<num[node]<<endl;
            return 1;
        }
        else
        {
            int temp=1;
            temp+=dfs(v[node][0]);
            num[node]=temp;
            //cout<<node<<": "<<num[node]<<endl;
            return num[node];
        }
    }
    else
    {
        int temp=1;
        for(int i=0;i<v[node].size();++i)
        {
            //cout<<"node: "<<v[node][i]<<endl;
            if(visited[v[node][i]]==false)
            {
                temp=temp+dfs(v[node][i]);
                //cout<<"bas: "<<temp<<endl;
            }
            else
                cout<<v[node][i]<<" is already visited."<<endl;
        }
        num[node]=temp;
        //cout<<node<<": "<<num[node]<<endl;
        return num[node];
    }
}

vector<int>v[1000];
int f[1000];
int ans=0;

*/
//const int inf=1000000007;
/*vector<vector<int> >adj(200005);
//vector<int>order;
//vector<vector<int> >group(500005);
//long long int desc[100005];
int subs[200005];
bool visited[200005];
int dfs(int node)
{
    visited[node]=true;
    order.push_back(node);
    subs[node]=1;
    //cout<<"here for: "<<node<<endl;
    if(adj[node].empty())
        return subs[node];
    for(int i=0;i<adj[node].size();++i)
    {
        if(!visited[adj[node][i]])
        {
            subs[node]+=dfs(adj[node][i]);
        }
    }
    return subs[node];
}*/
/*int arr[1000001];
int cumm[1000001][10];*/

/*vector<vector<int> >adj(26);
//string s[200005];
bool visited[26];

long long int dfs(int index)
{
    visited[index]=true;
    for(int i=0;i<adj[index].size();++i)
    {
        for(int j=0;j<s[adj[index][i]].size();++j)
        {
            if(!visited[s[adj[index][i]][j]-'a'])
                dfs(s[adj[index][i]][j]-'a');
        }
    }
}*/

/*vector<int> v,r;

int find_set(int x)
{
    if(v[x]==-1)
        return x;
    else
        return find_set(v[x]);
}

void union_set(int x, int y)
{
    x=find_set(x);
    y=find_set(y);
    if(x!=y)
    {
        if(r[x]>r[y])
        {
            r[x]+=r[y];
            v[y]=x;
        }
        else
        {
            r[y]+=r[x];
            v[x]=y;
        }
    }
}*/

//int cnt[400005],pref[400005];
/*int m;
vector<int>ans;
string s;

int dfs(int x,int y, int k)  //x=balance, y=curr_weight, k=step number
{
    if(k>m)
        return 1;
    for(int i=0;i<10;++i)
    {
        int f=0;
        if(s[i]=='1' && x>=0 && (i+1)!=y && x-i-1<0)
        {
            f=dfs(x-i-1,(i+1),k+1);
        }
        else if(s[i]=='1' && x<0 && (i+1)!=y && x+i+1>0)
        {
            f=dfs(x+i+1,(i+1),k+1);
        }
        if(f)
        {
            ans.push_back(i+1);
            return 1;
        }
    }
    return 0;
}

int n,m;
vector<vector<pair<long long int,long long int> > > adj(100005);
long long int numarr[100005],par[100005];
double carr[100005];

void dfs(int index, long long int sum, int num,int pi)
{
    if(carr[index]==-1 || numarr[index]==-1)
    {
        carr[index]=double(sum);
        numarr[index]=num;
        par[index]=pi;
    }
    else
    {
        if(numarr[index]==0)
        {
            carr[index]=sum;
            numarr[index]=num;
            par[index]=pi;
        }
        else if(carr[index]/numarr[index]>=(double(sum)/num))
        {
            carr[index]=sum;
            numarr[index]=num;
            par[index]=pi;
        }
    }
    for(int i=0;i<adj[index].size();++i)
    {
        double summer=adj[index][i].second;
        dfs(adj[index][i].first, carr[index]+summer,numarr[index]+1,index);
    }
}
*/
/*int n,k;
long long int sum[200005];
int counter[200005];*/
#define all(c) c.begin(),c.end()

/*vector<vector<int> >adj(100005);
bool visited[100005];
vector<int>path;
int n,a,b,da,db;
int dista=0,distb=0;

int traveller(int node)
{
    visited[node]=true;
    if(node==b-1)
    {
        return 1;
    }
    for(int i=0;i<adj[node].size();++i)
    {
        if(visited[adj[node][i]])
            continue;
        int val=traveller(adj[node][i]);
        if(val==1)
        {
            path.push_back(node);
            return 1;
        }
    }
    return 0;
}

void dfsa(int node,int ch)
{
    visited[node]=true;
    dista=max(dista,ch);
    for(int i=0;i<adj[node].size();++i)
    {
        if(!visited[adj[node][i]])
        {
            dfsa(adj[node][i],ch+1);
        }
    }
}
void dfsb(int node,int ch)
{
    visited[node]=true;
    distb=max(distb,ch);
    for(int i=0;i<adj[node].size();++i)
    {
        if(!visited[adj[node][i]])
        {
            dfsb(adj[node][i],ch+1);
        }
    }
}
*/

long long int mod=998244353;

//lli fact[300005];

/*void factorial()
{
    fact[0]=1;
    fact[1]=1;
    for(int i=2;i<300005;++i)
        fact[i]=(fact[i-1]*i);
    //cout<<"here"<<endl;
    return;
}
*/
long long int binpower(long long int a, long long int b)
{
    long long int ans=1;
    while(b>0)
    {
        if(b&1)
            ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}

bool isPrime(int n)
{
    for(int i=2;i*i<=n;++i)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
/*lli gprime[1000001];
void grsieve()
{
    memset(gprime,0,sizeof(gprime));
    gprime[1]=1;
    gprime[0]=0;
    for(lli i=2;i<1000001;++i)
    {
        if(gprime[i]==0)
        {
            for(lli j=i;j<1000001;j+=i)
                gprime[j]=i;
        }
    }
}*/


/*const int maxn=300001;
bool checkprimes[maxn];
//lli fact[maxn];
vector<lli>primes;
void primechecker()
{
    for(lli i=2;i<maxn;++i)
    {
        if(checkprimes[i]==false)
        {
            primes.pb(i);
            for(lli j=i;j<maxn;j+=i)
            {
                checkprimes[j]=true;
            }
        }
    }
}

void factcalc()
{
    fact[0]=1; fact[1]=1;
    for(lli i=2;i<maxn;++i)
    {
        fact[i]=(fact[i-1]*i)%mod;
    }
}

lli C(lli a, lli b)
{
    //cout<<mod<<endl;
    //cout<<a<<" fact[a]: "<<fact[a]<<endl;
    lli c=(fact[a]*fact[b-a])%mod;
    //cout<<c<<endl;
    //cout<<binpower(c,mod-2)<<endl;
    lli res=(fact[b]*binpower(c,mod-2))%mod;
    return res;
}*/

/*vector<vector<int> >adj(200005);   //1=>edge from curr to next, else edge from next to curr
bool visited[200005];

int dfs(int node)
{
    visited[node]=true;
    if(isuniv[node])
        subtree[node]=1;
    for(int i=0;i<adj[node].size();++i)
    {
        if(!visited[adj[node][i]])
        {
            subtree[node]+=dfs(adj[node][i]);
        }
    }
    return subtree[node];
}

void dfs2(int node)
{
    visited[node]=true;
    ans+=min(subtree[node],2*k-subtree[node]);
    for(int i=0;i<adj[node].size();++i)
    {
        if(!visited[adj[node][i]])
            dfs2(adj[node][i]);
    }
}
*/

/*
lli C(int u,int v)   //uCv
{
    lli c=(fact[v]*fact[u-v])%mod;
    lli in=binpower(c,mod-2);
    lli res=(in*fact[u])%mod;
    return res;
}
*/


int main()
{
    /*freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);*/
    iOS;
    lli test=1;
    cin>>test;
    while(test--)
    {
        lli k;
        cin>>k;
        if(k%2==1)
        {
            cout<<-1<<endl;
            continue;
        }
        lli l=k;
        int i=60;
        vector<int>v;
        while(i>1)
        {
            if(l>2*((1ll*1<<i)-1))
            {
                lli nm=(l-2)/(2*((1ll*1<<i)-1));
                l-=nm*(2*((1ll*1<<i)-1));
                //cout<<"printing "<<(1ll*1<<i)<<" "<<nm<<" times."<<endl;
                while(nm--)
                {
                    v.pb(i);
                }
            }
            i--;
        }
        if(l==1ll*6)
        {
            v.pb(1);v.pb(1);v.pb(1);
        }
        if(l==1ll*4)
        {
            //cout<<"here"<<endl;
            v.pb(1);
            v.pb(1);
        }
        if(l==1ll*2)
            v.pb(1);
        reverse(all(v));
        lli sum=0;
        for(int i=0;i<v.size();++i)
        {
            sum+=v[i];
        }
        cout<<sum<<endl;
        /*for(int i=0;i<v.size();++i)
            cout<<v[i]<<" ";
        cout<<endl;*/
        for(int i=0;i<v.size();++i)
        {
            for(int j=0;j<v[i]-1;++j)
                cout<<"0 ";
            cout<<"1 ";
        }
        cout<<endl;
    }
    /* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

    return 0;
}