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.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import java.util.HashSet;
import java.util.Arrays; 
import java.util.Scanner;
import java.util.Set;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.text.DecimalFormat;
import java.lang.Math;
import java.util.Iterator; 
import java.util.TreeSet;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.*;
public class Codeforces{
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static long MOD = (long)(1e9+7);
	static FastReader sc = new FastReader();
	static int pInf = Integer.MAX_VALUE;
	static int nInf = Integer.MIN_VALUE;
	public static void main(String[] args){
		int test = 1;
		test = sc.nextInt();
		while(test-->0){
			int n = sc.nextInt();
			int x = sc.nextInt();
			long sum = x;
			long xor = x;
			for(int i = 1; i < n; i++) {
				int y = sc.nextInt();
				sum += y;
				xor = xor^y;
			}
			out.println(2);
			out.println(xor+" "+(sum+xor));
		}
		out.close();
	}
	public static long mul(long a, long b){
	    return ((a%MOD)*(b%MOD))%MOD;
	}
	public static long add(long a, long b){
	    return ((a%MOD)+(b%MOD))%MOD;
	}
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Integer.lowestOneBit(i)   Equals k where k is the position of the first one in the binary
//Integer.highestOneBit(i)  Equals k where k is the position of the last one in the binary
//Integer.bitCount(i)       returns the number of one-bits
//Collections.sort(A,(p1,p2)->(int)(p2.x-p1.x)) To sort ArrayList in descending order wrt values of x.
//            Arrays.parallelSort(a,new Comparator<TPair>() {
//      		public int compare(TPair a,TPair b) {
//        			if(a.y==b.y) return a.x-b.x;
//        			return b.y-a.y;
//        		}
//        	});
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//PrimeFactors    
    public static ArrayList<Long> primeFactors(long n) {
        ArrayList<Long> arr = new ArrayList<>();
        if (n % 2 == 0)
            arr.add((long) 2);
        while (n % 2 == 0)
            n /= 2;
        for (long i = 3; i <= Math.sqrt(n); i += 2) {
            int flag = 0;
            while (n % i == 0) {
                n /= i;
                flag = 1;
            }
            if (flag == 1)
                arr.add(i);
        }
        if (n > 2)
            arr.add(n);
        return arr;
    }
//Pair Class
	static class Pair implements Comparable<Pair>{
		int x;
		int y;
		public Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
		@Override
		public int compareTo(Pair o) {
			if(this.x==o.x){
			    return (this.y-o.y);
			}
			return (this.x-o.x);
		}
	}
	static class TPair{
		int x;
		int y;
		int z;
		public TPair(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}
	}
//Merge Sort
	static void merge(long arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;
 
        /* Create temp arrays */
        long L[] = new long [n1];
        long R[] = new long [n2];
 
        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];
 
 
        /* Merge the temp arrays */
 
        // Initial indexes of first and second subarrays
        int i = 0, j = 0;
 
        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        /* Copy remaining elements of R[] if any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 
    // Main function that sorts arr[l..r] using
    // merge()
    static void sort(long arr[], int l, int r)
    {
        if (l < r)
        {
            // Find the middle point
            int m = (l+r)/2;
 
            // Sort first and second halves
            sort(arr, l, m);
            sort(arr , m+1, r);
 
            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
//Brian Kernighan’s Algorithm
    static long countSetBits(long n){
        if(n==0) return 0;
        return 1+countSetBits(n&(n-1));
    }
//Factorial
    static long factorial(long n){
        if(n==1) return 1;
        if(n==2) return 2;
        if(n==3) return 6;
        return n*factorial(n-1);
    }
//Euclidean Algorithm
    static long gcd(long A,long B){
        if(B==0) return A;
        return gcd(B,A%B);
    }
//Modular Exponentiation
    static long fastExpo(long x,long n){
        if(n==0) return 1;
        if((n&1)==0) return fastExpo((x*x)%MOD,n/2)%MOD;
        return ((x%MOD)*fastExpo((x*x)%MOD,(n-1)/2))%MOD;
    }
//AKS Algorithm
    static boolean isPrime(long n){
        if(n<=1) return false;
        if(n<=3) return true;
        if(n%2==0 || n%3==0) return false;
        for(int i=5;i<=Math.sqrt(n);i+=6)
            if(n%i==0 || n%(i+2)==0) return false;
        return true;
    }
//Reverse an array
    static <T> void reverse(T arr[],int l,int r){
    	Collections.reverse(Arrays.asList(arr).subList(l, r));
    }
//Sieve of eratosthenes
    static int[] findPrimes(int n){
        boolean isPrime[]=new boolean[n+1];
        ArrayList<Integer> a=new ArrayList<>();
        int result[];
        Arrays.fill(isPrime,true);
        isPrime[0]=false;
        isPrime[1]=false;
        for(int i=2;i*i<=n;++i){
            if(isPrime[i]==true){
                for(int j=i*i;j<=n;j+=i) isPrime[j]=false;
            }
        }
        for(int i=0;i<=n;i++) if(isPrime[i]==true) a.add(i);
        result=new int[a.size()];
        for(int i=0;i<a.size();i++) result[i]=a.get(i);
        return result;
        
    }
//Euler Totent function
    static long countCoprimes(long n){
        ArrayList<Long> prime_factors=new ArrayList<>();
        long x=n,flag=0;
        while(x%2==0){
            if(flag==0) prime_factors.add(2L);
            flag=1;
            x/=2;
        }
        for(long i=3;i*i<=x;i+=2){
            flag=0;
            while(x%i==0){
                if(flag==0) prime_factors.add(i);
                flag=1;
                x/=i;
            }
        }
        if(x>2) prime_factors.add(x);
        double ans=(double)n;
        for(Long p:prime_factors){
            ans*=(1.0-(Double)1.0/p);
        }
        return (long)ans;
    }
	static long modulo = (long)1e9+7;
	public static long modinv(long x){
	    return modpow(x, modulo-2);
	}
	public static long modpow(long a, long b){
	    if(b==0){
	        return 1;
	    }
	    long x = modpow(a, b/2);
	    x = (x*x)%modulo;
	    if(b%2==1){
	        return (x*a)%modulo;
	    }
	    return x;
	}
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		//it reads the data about the specified point and divide the data about it ,it is quite fast
		//than using direct 

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

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

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
}