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.*;

public class Main {
    static PrintWriter pw;
    static Scanner sc;
    static long ceildiv(long x, long y) { return (x+y-1)/y; }
    static int mod(long x, int m) { return (int)((x%m+m)%m); }
    static void put(TreeMap<Integer, Integer> map, Integer p){if(map.containsKey(p)) map.replace(p, map.get(p)+1); else map.put(p, 1); }
    static void rem(TreeMap<Integer, Integer> map, Integer p){ if(map.get(p)==1) map.remove(p);else map.replace(p, map.get(p)-1); }
    static void printf(double x, int dig){ String s="%."+dig+"f"; pw.printf(s, x); }
    static int Int(boolean x){ return x?1:0; }
    static final int inf=(int)1e9, mod=998244353;
    static final long infL=inf*1l*inf;
    static final double r2=Math.sqrt(2), eps=1e-9;
    static int[][] dp;
    static TreeSet<String> permutations;
    public static long gcd(long x, long y) { return y==0? x: gcd(y, x%y); }
    public static void main(String[] args) throws IOException {
        sc=new Scanner(System.in);
        pw=new PrintWriter(System.out);
        int t=sc.nextInt();
        while(t-->0){
            solve();
        }
        pw.close();
    }
    static ArrayList<Integer> list;
    static void solve() throws IOException{
        long n=sc.nextLong();
        int ans=1;
        if(n<0 || n%2==1){
            pw.println(-1);
            return;
        }
        list=new ArrayList<>();
        solve(n);
        pw.println(list.size());
        printArr(list);
    }
    static void solve(long x){
        if(x==0)
            return;
        long ans=2, val=4;
        int c=1;
        while(ans<x){
            ans+=val;
            val*=2;
            c++;
        }
        if(ans>x){
            ans-=val/2;
            c--;
        }
        list.add(1);
        while(c-->1)
            list.add(0);
        solve(x-ans);
    }
    static void printArr(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++)
            pw.print(arr[i] + " ");
        pw.println(arr[arr.length - 1]);
    }
    static void printArr(long[] arr) {
        for (int i = 0; i < arr.length - 1; i++)
            pw.print(arr[i] + " ");
        pw.println(arr[arr.length - 1]);
    }
    static void printArr(double[] arr) {
        for (int i = 0; i < arr.length - 1; i++)
            pw.print(arr[i] + " ");
        pw.println(arr[arr.length - 1]);
    }
    static void printArr(Integer[] arr) {
        for (int i = 0; i < arr.length; i++)
            pw.print(arr[i] + " ");
        pw.println();
    }
    static void printArr(ArrayList<Integer> list) {
        for (int i = 0; i < list.size(); i++)
            pw.print(list.get(i)+" ");
        pw.println();
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;
        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
        public int[] nextDigits() throws IOException{
            String s=nextLine();
            int[] arr=new int[s.length()];
            for(int i=0; i<arr.length; i++)
                arr[i]=s.charAt(i)-'0';
            return arr;
        }
        public int[] nextArr(int n) throws IOException {
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++)
                arr[i] = nextInt();
            return arr;
        }
        public Integer[] nextsort(int n) throws IOException{
            Integer[] arr=new Integer[n];
            for(int i=0; i<n; i++)
                arr[i]=nextInt();
            return arr;
        }
        public Pair nextPair() throws IOException{
            return new Pair(nextInt(), nextInt());
        }
        public Pair[] nextPairArr(int n) throws IOException{
            Pair[] arr=new Pair[n];
            for(int i=0; i<n; i++)
                arr[i]=nextPair();
            return arr;
        }
        public boolean ready() throws IOException {
            return br.ready();
        }
    }
    static class Pair implements Comparable<Pair>{
        int x;
        int y;
        public Pair(int x, int y) {
            this.x=x;
            this.y=y;
        }
        public boolean contains(int a){
            return x==a || y==a;
        }
        public int hashCode() {
            return (this.x*1000000000+this.y);
        }
        public int compareTo(Pair p){
            return y-p.y;
        }
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (this.getClass() != obj.getClass()) {
                return false;
            }
            Pair p = (Pair) obj;
            return this.x==p.x && this.y==p.y;
        }
        public Pair clone(){
            return new Pair(x, y);
        }
        public String toString(){
            return this.x+" "+this.y;
        }
        public void add(Pair p){
            x+=p.x;
            y+=p.y;
        }
    }
    static class LP implements Comparable<LP>{
        long x, y;
        public LP(long a, long b){
            x=a;
            y=b;
        }
        public void add(LP p){
            x+=p.x;
            y+=p.y;
        }
        public boolean equals(LP p){
            return p.x==x && y==p.y;
        }
        public String toString(){
            return this.x+" "+this.y;
        }
        public int compareTo(LP p){
            int a=Long.compare(x, p.x);
            if(a!=0)
                return a;
            return Long.compare(y, p.y);
        }
    }
    static class Triple implements Comparable<Triple>{
        int x, y, z;
        public Triple(int a, int b, int c){
            x=a;
            y=b;
            z=c;
        }
        public int compareTo(Triple t){
            if(this.y!=t.y)
                return y-t.y;
            return x-t.x;
        }
        public String toString(){
            return x+" "+y+" "+z;
        }
    }
    static class sqrtDec{
        int[] arr;
        long[] sqrt;
        Pair[] range;
        public sqrtDec(int[] a){
            arr=a;
            int n=sqrt(a.length);
            sqrt=new long[n];
            range=new Pair[n];
            for(int i=0; i<n; i++){
                for(int j=i*n, k=0; k<n && j+k <arr.length; k++)
                    sqrt[i]+=arr[j+k];
                range[i]=new Pair(i*n, (i+1)*n-1);
            }
        }
        public int sqrt(int x){
            int st=1, end=x;
            int ans=0;
            while(st<=end){
                int mid=(st+end)/2;
                if(sq(mid)>=x){
                    ans=mid;
                    end=mid-1;
                }else{
                    st=mid+1;
                }
            }
            return ans;
        }
        public long sq(long x){
            return x*x;
        }
        public Pair range(int l, int r){
            int st=0, end=range.length-1;
            Pair ans=new Pair(0, 0);
            while(st<=end){
                int mid=(st+end)/2;
                if(range[mid].x<=l){
                    ans.x=mid;
                    st=mid+1;
                }else{
                    end=mid-1;
                }
            }
            st=0; end=range.length-1;
            while(st<=end){
                int mid=(st+end)/2;
                if(range[mid].y>=r){
                    ans.y=mid;
                    end=mid-1;
                }else{
                    st=mid+1;
                }
            }
            return ans;
        }
        public long query(int l, int r){
            Pair p=range(l, r);
            long ans=0;
            for(int i=p.x; i<=p.y; i++){
                if(notAll(l, r, range[i])){
                    for(int j=range[i].x; j<=range[i].y; j++){
                        if(j>=l && j<=r)
                            ans+=arr[j];
                    }
                }else{
                    ans+=sqrt[i];
                }
            }
            return ans;
        }
        static boolean notAll(int l, int r, Pair p){
            return l>=p.x || r<=p.y;
        }
    }
}