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 JAVA):

Solution:
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class AvoidTrygub {
    public static void main(String[] args) throws IOException {
        // InputStream inputStream = new FileInputStream("input.txt");
        // OutputStream outputStream = new FileOutputStream("output.txt");
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(in.nextInt(), in, out);
        out.close();
    }
    static class TaskA {
        long mod = (long)(1e9) + 7;
        long fact[];
        int depth[];
        int parentTable[][];
        int degree[];
        ArrayList<Integer> leaves;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int diam = 0;

        int r[] = {1 , 0 , -1 , 0};
        int c[] = {0 , 1 , 0 , -1};

        int res = 0;

        public void solve(int testNumber, InputReader in, PrintWriter out) throws IOException {
            while(testNumber-->0){
                long n = in.nextLong();
                if(n%2 == 1){
                    out.println(-1);
                    continue;
                }
                ArrayList<Integer> ans = new ArrayList<>();
                ans.add(1);
                long now = 2;
                n-=2;
                while(n>0){
                    if(n >= now*2){
                        now *= 2;
                        n-=now;
                        ans.add(0);
                    }
                    else{
                        now = 2;
                        n-=2;
                        ans.add(1);
                    }
                }
                out.println(ans.size());
                for(int i:ans)
                    out.print(i + " ");
                out.println();
            }
        }

        public void dfs(char a[][] , int no[][] , int count , int x , int y){
            // int ans = 0;
            if(no[x][y] != 0)
                return;
            no[x][y] = count;
            for(int i=0;i<4;i++){
                int newx = x+r[i];
                int newy = y+c[i];
                if(newx>=0 && newx<a.length && newy>=0 && newy<a[x].length){
                    if(a[newx][newy] == '*')
                        res++;
                    else
                        dfs(a , no , count , newx , newy);
                }
            }
        }

        public int height(long x){
            int count = 0;
            long p = x;
            while(p!=1){
                p/=2;
                count++;
            }
            return count;
        }

        public void update(char a[][] , int count[][] , int i , int j , Stack<int[]> s[]){
            int sum = 0;
            int n = a.length;
            int prev = count[i][j];
            for(int k=j-2;k<=j;k++){
                if(k<0)
                    continue;
                int inner = 0;
                for(int l=0;l<3;l++){
                    if(k+l<n && a[i][k+l] == 'X')
                        inner++;
                }
                if(inner == 3)
                    sum++;
            }

            for(int k=i-2;k<=i;k++){
                if(k<0)
                    continue;
                int inner = 0;
                for(int l=0;l<3;l++){
                    if(k+l<n && a[k+l][j] == 'X')
                        inner++;
                }
                if(inner == 3)
                    sum++;
            }
            count[i][j] = sum;
            if(sum<prev)
                s[sum].push(new int[]{i , j});
        }

        public int[][] generate(char a[][]){
            int n = a.length;
            int count[][] = new int[n][n];
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(a[i][j] == '.')
                        continue;
                    int sum = 0;
                    for(int k=j-2;k<=j;k++){
                        if(k<0)
                            continue;
                        int inner = 0;
                        for(int l=0;l<3;l++){
                            if(k+l<n && a[i][k+l] == 'X')
                                inner++;
                        }
                        if(inner == 3)
                            sum++;
                    }

                    for(int k=i-2;k<=i;k++){
                        if(k<0)
                            continue;
                        int inner = 0;
                        for(int l=0;l<3;l++){
                            if(k+l<n && a[k+l][j] == 'X')
                                inner++;
                        }
                        if(inner == 3)
                            sum++;
                    }
                    count[i][j] = sum;
                }
            }
            return count;
        }

        public boolean valid(int x , int y , int n , char a[][]){
            
            if(!((x>=0 && x<n && y>=0 && y<n)))
                return false;

            int count = 0;
            for(int i=x-2;i<=x;i++)
                if(i>=0 && a[i][y] == 'O')
                    count++;
            if(count == 3)
                return false;

            count = 0;
            for(int i=x+2;i>=x;i--)
                if(i<n && a[i][y] == 'O')
                    count++;
            if(count == 3)
                return false;

            count = 0;
            for(int j=y-2;j<=y;j++)
                if(j>=0 && a[x][j] == 'O')
                    count++;
            if(count == 3)
                return false;

            count = 0;
            for(int j=y+2;j>=y;j--)
                if(j<n && a[x][j] == 'O')
                    count++;
            if(count == 3)
                return false;

            return true;
        }

        public Stack<int[]>[] getS(int count[][]){
            int n = count.length;
            Stack<int[]> s[] = new Stack[10];
            for(int i=0;i<10;i++)
                s[i] = new Stack<>();

            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    int index = count[i][j];
                    s[index].push(new int[]{i , j});
                }
            }
            return s;
        }

        class Sort implements Comparator<int[]>{
        	public int compare(int a[] , int b[]){
        		return a[0]+a[1] - b[0] - b[1];
        	}
        }

        public int lower(ArrayList<Integer> a , int x){
            if(a.size() == 0)
                return 0;
            if(a.get(a.size()-1) < x)
                return a.size();
            int l = 0;
            int r = a.size()-1;
            while(l<=r){
                int mid = (l+r)>>1;
                if(a.get(mid)>=x && (mid<1 || a.get(mid-1)<x))
                    return mid;
                else if(a.get(mid) < x)
                    l = mid+1;
                else
                    r = mid-1;
            }
            return -1;
        }

        public int distance(ArrayList<ArrayList<Integer>> a , int u , int v){
            return depth[u]+depth[v] - 2*depth[lca(a , u , v)];
        }

        public int lca(ArrayList<ArrayList<Integer>> a , int u , int v){
            if(depth[v]<depth[u]){
                int x = u;
                u = v;
                v = x;
            }
            int diff = depth[v] - depth[u];
            for(int i=0;i<parentTable[v].length;i++){
                // checking whether the ith bit is set in the diff variable
                if(((diff>>i)&1) == 1)
                    v = parentTable[v][i];
            }
            if(v == u)
                return v;
            for(int i=parentTable[v].length-1;i>=0;i--){
                if(parentTable[u][i] != parentTable[v][i]){
                    v = parentTable[v][i];
                    u = parentTable[u][i];
                }
            }
            return parentTable[u][0];
        }
        

        public int[][] multiply(int a[][] , int b[][]){
            int c[][] = new int[a.length][b[0].length];
            for(int i=0;i<a.length;i++){
                for(int j=0;j<b[0].length;j++){
                    for(int k=0;k<b.length;k++)
                        c[i][j] += a[i][k]*b[k][j];
                }
            }
            return c;
        }

        public int[][] multiply(int a[][] , int b[][] , int mod){
            int c[][] = new int[a.length][b[0].length];
            for(int i=0;i<a.length;i++){
                for(int j=0;j<b[0].length;j++){
                    for(int k=0;k<b.length;k++){
                        c[i][j] += a[i][k]*b[k][j];
                        c[i][j]%=mod;
                    }
                }
            }
            return c;
        }

        public int[][] pow(int a[][] , long b){
            int res[][] = new int[a.length][a[0].length];
            for(int i=0;i<a.length;i++)
                res[i][i] = 1;
            while(b>0){
                if((b&1) == 1)
                    res = multiply(res , a , 10);
                a = multiply(a , a , 10);
                b>>=1;
            }
            return res;
        }

        

        // for the min max problems
        public void build(int lookup[][] , int arr[], int n) { 
            for (int i = 0; i < n; i++) 
                lookup[i][0] = arr[i]; 
            for (int j = 1; (1 << j) <= n; j++) { 
                for (int i = 0; (i + (1 << j) - 1) < n; i++) { 
                    if (lookup[i][j - 1] > lookup[i + (1 << (j - 1))][j - 1]) 
                        lookup[i][j] = lookup[i][j - 1]; 
                    else
                        lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1]; 
                } 
            } 
        }
        public int query(int lookup[][] , int L, int R) { 
            int j = (int)(Math.log(R - L + 1)/Math.log(2)); 
            if (lookup[L][j] >= lookup[R - (1 << j) + 1][j]) 
                return lookup[L][j]; 
            else
                return lookup[R - (1 << j) + 1][j]; 
        }

        // for printing purposes
        public void print1d(int a[] , PrintWriter out){
            for(int i=0;i<a.length;i++)
                out.print(a[i]);
            out.println();
        }
        public void print1d(long a[] , PrintWriter out){
            for(int i=0;i<a.length;i++)
                out.print(a[i] + " ");
            out.println();
        }
        public void print2d(int a[][] , PrintWriter out){
            for(int i=0;i<a.length;i++){
                for(int j=0;j<a[i].length;j++)
                    out.print(a[i][j] + " ");
                out.println();
            }
            // out.println();
        }
        public void print2d(char a[][] , PrintWriter out){
            for(int i=0;i<a.length;i++){
                for(int j=0;j<a[i].length;j++)
                    out.print(a[i][j]);
                out.println();
            }
            // out.println();
        }


        public void sieve(int a[]){
            a[0] = a[1] = 1;
            int i;
            for(i=2;i*i<=a.length;i++){
                if(a[i] != 0)
                    continue;
                a[i] = i;
                for(int k = (i)*(i);k<a.length;k+=i){
                    if(a[k] != 0)
                        continue;
                    a[k] = i;
                }
            }
        }

        public long nCrPFermet(int n , int r , long p){
            if(r==0)
                return 1l;
            // long fact[] = new long[n+1];
            // fact[0] = 1;
            // for(int i=1;i<=n;i++)
            //     fact[i] = (i*fact[i-1])%p;
            long modInverseR = pow(fact[r] , p-2 , p);
            long modInverseNR = pow(fact[n-r] , p-2 , p);
            long w = (((fact[n]*modInverseR)%p)*modInverseNR)%p;
            return w;
        }
        public long pow(long a, long b, long m) {
            a %= m;
            long res = 1;
            while (b > 0) {
                long x = b&1;
                if (x == 1)
                    res = res * a % m;
                a = a * a % m;
                b >>= 1;
            }
            return res;
        }
        public long pow(long a, long b) {
            long res = 1;
            while (b > 0) {
                long x = b&1;
                if (x == 1)
                    res = res * a;
                a = a * a;
                b >>= 1;
            }
            return res;
        }
        public void sortedArrayToBST(TreeSet<Integer> a , int start, int end) { 
            if (start > end) {
                return;
            }
            int mid = (start + end) / 2;
            a.add(mid);
            sortedArrayToBST(a, start, mid - 1);
            sortedArrayToBST(a, mid + 1, end); 
        }
        class Combine{
            int value;
            int delete;
            Combine(int val , int delete){
                this.value = val;
                this.delete = delete;
            }
        }
        class Sort2 implements Comparator<Combine>{
            public int compare(Combine a , Combine b){
                if(a.value > b.value)
                    return 1;
                else if(a.value == b.value && a.delete>b.delete)
                    return 1;
                else if(a.value == b.value && a.delete == b.delete)
                    return 0;
                return -1;
            }
        }
        public int lowerLastBound(ArrayList<Integer> a , int x){
            int l = 0;
            int r = a.size()-1;
            if(a.get(l)>=x)
                return -1;
            if(a.get(r)<x)
                return r;
            int mid = -1;
            while(l<=r){
                mid = (l+r)/2;
                if(a.get(mid) == x && a.get(mid-1)<x)
                    return mid-1;
                else if(a.get(mid)>=x)
                    r = mid-1;
                else if(a.get(mid)<x && a.get(mid+1)>=x)
                    return mid;
                else if(a.get(mid)<x && a.get(mid+1)<x)
                    l = mid+1;
            }
            return mid;
        }
        public int upperFirstBound(ArrayList<Integer> a , int x){
            int l = 0;
            int r = a.size()-1;
            if(a.get(l)>x)
                return l;
            if(a.get(r)<=x)
                return r+1;
            int mid = -1;
            while(l<=r){
                mid = (l+r)/2;
                if(a.get(mid) == x && a.get(mid+1)>x)
                    return mid+1;
                else if(a.get(mid)<=x)
                    l = mid+1;
                else if(a.get(mid)>x && a.get(mid-1)<=x)
                    return mid;
                else if(a.get(mid)>x && a.get(mid-1)>x)
                    r = mid-1;
            }
            return mid;
        }
        public int lowerLastBound(long a[] , long x){
            int l = 0;
            int r = a.length-1;
            if(a[l]>=x)
                return -1;
            if(a[r]<x)
                return r;
            int mid = -1;
            while(l<=r){
                mid = (l+r)/2;
                if(a[mid] == x && a[mid-1]<x)
                    return mid-1;
                else if(a[mid]>=x)
                    r = mid-1;
                else if(a[mid]<x && a[mid+1]>=x)
                    return mid;
                else if(a[mid]<x && a[mid+1]<x)
                    l = mid+1;
            }
            return mid;
        }
        public int upperFirstBound(long a[] , long x){
            int l = 0;
            int r = a.length-1;
            if(a[l]>x)
                return l;
            if(a[r]<=x)
                return r+1;
            int mid = -1;
            while(l<=r){
                mid = (l+r)/2;
                if(a[mid] == x && a[mid+1]>x)
                    return mid+1;
                else if(a[mid]<=x)
                    l = mid+1;
                else if(a[mid]>x && a[mid-1]<=x)
                    return mid;
                else if(a[mid]>x && a[mid-1]>x)
                    r = mid-1;
            }
            return mid;
        }
        public long log(float number , int base){
            return (long) Math.ceil((Math.log(number) / Math.log(base)) + 1e-9);
        }
        public long gcd(long a , long b){
            if(a<b){
                long c = b;
                b = a;
                a = c;
            }
            while(b!=0){
                long c = a;
                a = b;
                b = c%a;
            }
            return a;
        }
        public long[] gcdEx(long p, long q) {
            if (q == 0)
                return new long[] { p, 1, 0 };
            long[] vals = gcdEx(q, p % q);
            long d = vals[0];
            long a = vals[2];
            long b = vals[1] - (p / q) * vals[2];
            // 0->gcd 1->xValue 2->yValue
            return new long[] { d, a, b };
        }
        public void sievePhi(int a[]){
            a[0] = 0;
            a[1] = 1;
            for(int i=2;i<a.length;i++)
                a[i] = i-1;
            for(int i=2;i<a.length;i++)
                for(int j = 2*i;j<a.length;j+=i)
                    a[j] -= a[i];
        }
        public void lcmSum(long a[]){
            int sievePhi[] = new int[(int)1e6 + 1];
            sievePhi(sievePhi);
            a[0] = 0;
            for(int i=1;i<a.length;i++)
                for(int j = i;j<a.length;j+=i)
                    a[j] += (long)i*sievePhi[i];
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}