Problem: Let's call an array a_1, a_2, ..., a_m of nonnegative integer numbers good if a_1 + a_2 + ... + a_m = 2⋅(a_1 ⊕ a_2 ⊕ ... ⊕ a_m), where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

For example, array [1, 2, 3, 6] is good, as 1 + 2 + 3 + 6 = 12 = 2⋅ 6 = 2⋅ (1⊕ 2 ⊕ 3 ⊕ 6). At the same time, array [1, 2, 1, 3] isn't good, as 1 + 2 + 1 + 3 = 7 ≠ 2⋅ 1 = 2⋅(1⊕ 2 ⊕ 1 ⊕ 3).

You are given an array of length n: a_1, a_2, ..., a_n. Append at most 3 elements to it to make it good. Appended elements don't have to be different. It can be shown that the solution always exists under the given constraints. If there are different solutions, you are allowed to output any of them. Note that you don't have to minimize the number of added elements!. So, if an array is good already you are allowed to not append elements.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10 000). The description of the test cases follows.

The first line of each test case contains a single integer n (1≤ n ≤ 10^5) — the size of the array.

The second line of each test case contains n integers a_1, a_2, ..., a_n (0≤ a_i ≤ 10^9) — the elements of the array.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Output

For each test case, output two lines.

In the first line, output a single integer s (0≤ s≤ 3) — the number of elements you want to append.

In the second line, output s integers b_1, ..., b_s (0≤ b_i ≤ 10^{18}) — the elements you want to append to the array.

If there are different solutions, you are allowed to output any of them.

Example

Input


3
4
1 2 3 6
1
8
2
1 1


Output


0

2
4 4
3
2 6 2

Note

In the first test case of the example, the sum of all numbers is 12, and their ⊕ is 6, so the condition is already satisfied.

In the second test case of the example, after adding 4, 4, the array becomes [8, 4, 4]. The sum of numbers in it is 16, ⊕ of numbers in it is 8.

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.BigInteger;
import java.util.*;

// written by luchy0120

public class Main {
    public static void main(String[] args) throws Exception {

        new Main().run();
    }

    static int groups = 0;
    static int[] fa;
    static int[] sz;

    static void init(int n) {
        groups = n;
        fa = new int[n];
        for (int i = 1; i < n; ++i) {
            fa[i] = i;
        }
        sz = new int[n];
        Arrays.fill(sz, 1);
    }

    static int root(int p) {
        while (p != fa[p]) {
            fa[p] = fa[fa[p]];
            p = fa[p];
        }
        return p;
    }

    static void combine(int p, int q) {
        int i = root(p);
        int j = root(q);
        if (i == j) {
            return;
        }
        if (sz[i] < sz[j]) {
            fa[i] = j;
            sz[j] += sz[i];
        } else {
            fa[j] = i;
            sz[i] += sz[j];
        }
        groups--;
    }


    int color[],dfn[],low[],stack[],cnt[];
    boolean vis[];
    boolean iscut[];
    int deep,top,n,m,sum,ans;
    List<Integer> g[];

    void tarjan(int u,int fa) {
        int child = 0;
        dfn[u]=++deep;
        low[u]=deep;
        vis[u]=true;
        stack[++top]=u;
        int sz=g[u].size();
        for(int i=0;i<sz;i++) {
            int v =g[u].get(i);
            if(v==fa) continue;
            if(dfn[v]==0) {
                child++;
                tarjan(v,u);
                low[u]=Math.min(low[u],low[v]);
            } else {
                if(vis[v]) {
                    low[u]=Math.min(low[u],low[v]);
                }
            }
        }
        if(fa<0&&child==1){
            iscut[u] =true;
        }

        if(dfn[u]==low[u]) {
            iscut[u] = true;
            color[u]=++sum;
            vis[u]=false;
            while(stack[top]!=u) {
                color[stack[top]]=sum;
                vis[stack[top--]]=false;
            }
            top--;
        }
    }


    int h[],to[],ne[];int ct =0;
    void add(int u,int v){
        u--;v--;
        to[ct] = v;
        ne[ct] = h[u];
        h[u] = ct++;
    }

    void graph(int n,int m){
        h = new int[n];
        Arrays.fill(h,-1);
        ne = new int[2*m];
        to = new int[2*m];
        ct = 0;
    }


    static long mul(long a, long b, long p)
    {
        long res=0,base=a;
        while(b>0)
        {
            if((b&1L)>0)
                res=(res+base)%p;
            base=(base+base)%p;
            b>>=1;
        }
        return res;
    }


    static long mod_pow(long k,long n,long p){
        long res = 1L;
        long temp = (k%p+p)%p;
        while(n!=0L){
            if((n&1L)==1L){
                res = ((res*temp)%p+p)%p;
            }
            temp = ((temp * temp)%p+p)%p;
            n = n>>1L;
        }
        return res%p;
    }
    public static String roundS(double result, int scale){
        String fmt = String.format("%%.%df", scale);
        return String.format(fmt, result);
    }

    int x[];
    int y[];
    int k ;
    int r = 1000000000;
    int[][] pos;

    boolean gd(int i){
        if(pos[i][0]<pos[i][1]) return false;
        if(pos[i][2]>pos[i][3]) return false;
        return true;
    }


    int area(int i){
        if(pos[i][0]<=pos[i][1]) return 0;
        if(pos[i][2]>=pos[i][3]) return 0;
        return (pos[i][0]-pos[i][1])*(pos[i][3]-pos[i][2]);
    }

    boolean in(int i,int y,int x){
        return y<=pos[i][0]&&y>=pos[i][1] && x<=pos[i][3] && x>= pos[i][2];
    }


    boolean ck(int i,int j){
        return !in(i, pos[j][0],pos[j][3]) &&
        !in(i, pos[j][0],pos[j][2]) &&
        !in(i, pos[j][1],pos[j][2]) &&
        !in(i, pos[j][1],pos[j][3]);
    }

    void go(int c,int sum){
        if(sum>=r) return;
        if(c==n){
            for(int i=0;i<k;++i) {
                if (!gd(i)) return;
            }

            for(int i=0;i<k;++i){
                for(int j=i+1;j<k;++j){
                    if(!ck(i,j)){
                        return;
                    }
                }
            }
            r = sum;
            return;
        }

        for(int i=0;i<k;++i){
            int tmp[] = pos[i].clone();
            int zx = x[c];
            int zy = y[c];

            int prev = area(i);

            pos[i][0] = Math.max(pos[i][0],zy);
            pos[i][1] = Math.min(pos[i][1],zy);

            pos[i][2] = Math.min(pos[i][2],zx);
            pos[i][3] = Math.max(pos[i][3],zx);

            int cur = area(i);

            go(c+1,sum-prev+cur);

            pos[i] = tmp;
        }

    }


    int dx[] = {0,0,1,-1};
    int dy[] = {1,-1,0,0};
    boolean xiao(int mp[][]){
        boolean ok = false;
        boolean mk[][] = new boolean[7][5];
        for(int i=0;i<7;++i){
            for(int j=0;j<5;++j){
                if(mp[i][j]==0) continue;
                int k = j+1;
                int c = mp[i][j];
                while(k<5&&mp[i][k]==c) k++;
                if(k-j>=3){
                    ok = true;
                    for(int u=j;u<k;++u){
                        mk[i][u] = true;
                    }
                }
            }
        }

        for(int i=0;i<5;++i){
            for(int j=6;j>=0;--j){
                if(mp[i][j]==0) break;
                int k = j-1;
                int c = mp[i][j];
                while(k>=0&&mp[i][k]==c) k--;
                if(j-k>=3){
                    ok = true;
                    for(int u=j;u>k;--u){
                        mk[i][u] = true;
                    }
                }
            }
        }

        for(int i=0;i<7;++i) {
            for (int j = 0; j < 5; ++j) {
                if (mp[i][j] > 0 && mk[i][j]) {
                    mp[i][j] = 0;
                }
            }
        }
      return ok;
    }

    void luo(int[][] mp){
        for(int i=0;i<5;++i){
            int f = 6;
            for(int j=6;j>=0;--j){
                if(mp[i][j]==0) continue;
                mp[i][f] = mp[i][j];f--;
                mp[i][j] = 0;
            }
        }
    }


    void go(int mp[][]){
        while(xiao(mp)){
            luo(mp);
        }



    }


    void solve() {
//        int n = ni();
//        int mp[][] = new int[7][5];
//        // less than 10;
//
//        for(int i=0;i<5;++i){
//            int x = 6;
//            while(true){
//                int num = ni();
//                if(num==0) break;
//                mp[x][i] = num;
//                x--;
//            }
//        }

        int t = ni();
        for(int j=0;j<t;++j) {
            int n = ni();
            long a[] =nal(n);
            long s = 0;
            long r = 0;
            for(int i=0;i<n;++i){
                s += a[i];
                r ^= a[i];
            }
            if(s%2==0){
                long v1 = 1L<<59L;
                s += v1;
                r ^= v1;
                long v2 = (2L*r-s)/2;
                println(3);
                println(v1 + " " +v2+" "+v2);
            }else{
                long v1 = 1L<<59L;
                v1++;
                s += v1;
                r ^= v1;
                long v2 = (2*r-s)/2;
                println(3);
                println(v1 + " " +v2+" "+v2);
            }
        }









    }





    InputStream is;
    PrintWriter out;

    void run() throws Exception {
        is = System.in;
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }

    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;

    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {
                lenbuf = is.read(inbuf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];
    }

    private boolean isSpaceChar(int c) {
        return !(c >= 33 && c <= 126);
    }

    private int skip() {
        int b;
        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
        return b;
    }

    private double nd() {
        return Double.parseDouble(ns());
    }

    private char nc() {
        return (char) skip();
    }

    private char ncc() {
        int b = readByte();
        return (char) b;
    }

    private String ns() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[] ns(int n) {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) {
            buf[p++] = (char) b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }

    private String nline() {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    private char[][] nm(int n, int m) {
        char[][] a = new char[n][];
        for (int i = 0; i < n; i++) a[i] = ns(m);
        return a;
    }

    private int[] na(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = ni();
        return a;
    }

    private long[] nal(int n) {
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = nl();
        return a;
    }

    private int ni() {
        int num = 0, b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) {
        }
        ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();
        }
    }

    private long nl() {
        long num = 0;
        int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) {
        }
        ;
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while (true) {
            if (b >= '0' && b <= '9') num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();
        }
    }

    void print(Object obj) {
        out.print(obj);
    }

    void println(Object obj) {
        out.println(obj);
    }

    void println() {
        out.println();
    }

    void printArray(int a[],int from){
        int l = a.length;
        for(int i=from;i<l;++i){
            print(a[i]);
            if(i!=l-1){
                print(" ");
            }
        }
        println();
    }

    void printArray(long a[],int from){
        int l = a.length;
        for(int i=from;i<l;++i){
            print(a[i]);
            if(i!=l-1){
                print(" ");
            }
        }
        println();
    }
}