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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.*;
public class pcarp{
	static int  max_value;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-->0){
			int n = sc.nextInt();
		    long [] arr = new long[n];
		    for(int i=0;i<n;i++){
		    	arr[i]=sc.nextLong();
		    }
		    long sum=0;
		    long xor=0;
		    for(long x : arr){
		    	sum+=x;
		    	xor^=x;
		    }
		   // System.out.println(sum+" "+xor);
		    if(sum==2*xor){
		    	System.out.println(0);
		    	System.out.println();
		    }
		    else{
		    	System.out.println(2);
		    	System.out.println(xor+" "+(sum+xor));
		    	//System.out.println(sum+xor);
		    }
			
		}
	}
	static void function(int l, int r, int[] arr, int[] depth, int d){
		if(r<l){
			return;
		}
		if(r==l){
			depth[l]=d;
			return;
		}
		int m = l;
		for(int i=l+1;i<=r;i++){
			if(arr[m]<arr[i]){
				m=i;
			}
		}
		depth[m]=d;
		function(l,m-1,arr,depth,d+1);
		function(m+1,r,arr,depth,d+1);
	}
	static boolean perfectCube(long N)
    {
        long cube_root;
        cube_root = (long)Math.round(Math.cbrt(N));
     
        // If cube of cube_root is equals to N,
        // then print Yes Else print No
        if (cube_root * cube_root * cube_root == N) {
            return true;
        }
        return false;
    }
	public static int value(int n){
		if(n==0){
			return 0;
		}
		int cnt=0;
		while(n>0){
			cnt++;
			n/=2;
		}
		return cnt;
	}
	public static int value1(int n){
		int cnt=0;
		while(n>1){
			cnt++;
			n/=2;
		}
		return cnt;
	}
	public static String function(String s){

		if(check(s)){
			return s;
		}
		if(s.length()==2 && s.charAt(0)==s.charAt(1)){
			return "";
		}
		if(s.charAt(0)==s.charAt(1)){
			return function(s.substring(2,s.length()));
		}
		else{
			return function(s.charAt(0)+function(s.substring(1,s.length())));
		}
	}

	static boolean isPowerOfTwo(int n){
    	if(n==0)
    		return false;
 
		return (int)(Math.ceil((Math.log(n) / Math.log(2)))) == 
       			(int)(Math.floor(((Math.log(n) / Math.log(2)))));
	}
	static boolean isPerfectSquare(double x)
    {
        if (x >= 0) {
            double sr = Math.sqrt(x);
            return ((sr * sr) == x);
        }
        return false;
    }
	public static boolean isPerfect(int n){
		int a = (int)Math.sqrt(n);
		if(a*a==n){
			return true;
		}
		return false;
	}
	public static boolean check(String s){
		if(s.length()==1){
			return true;
		}
		for(int i=1;i<s.length();i++){
			if(s.charAt(i)==s.charAt(i-1)){
				return false;
			}
		}
		return true;
	}
	public static boolean isPrime(int n){
		boolean flag=true;
		while(n%2==0){
			n=n/2;
			flag=false;
		}
		for(int i=3;i<=Math.sqrt(n);i+=2){
			if(n%i==0){
				flag=false;
				while(n%i==0){
					n=n/i;
				}
			}
		}
		return flag;
	}
	public static void dfst(ArrayList<ArrayList<Integer>> graph,int src, int deg,boolean ef, boolean of, boolean[] vis, boolean[] flip, int[] init, int[] goal){
		if(vis[src]){
			return;
		}
		vis[src]=true;
		if((deg%2==0 && ef) || (deg%2==1 && of)){
			init[src]=1-init[src];
		}
		if(init[src]!=goal[src]){
			flip[src]=true;
			if(deg%2==0){
				ef=!ef;
			}
			else{
				of=!of;
			}
		}
		for(int i=0;i<graph.get(src).size();i++){
			if(!vis[graph.get(src).get(i)]){
				dfst(graph,graph.get(src).get(i),deg+1,ef,of,vis,flip,init,goal);
			}
		}
	}
	public static void dfs(ArrayList<ArrayList<Integer>> graph, int src, int val, boolean[] vis){
		vis[src]=true;
		int cur_val =0;
		for(int i=0;i<graph.get(src).size();i++){
			if(!vis[graph.get(src).get(i)]){
				cur_val=val+1;
				dfs(graph,graph.get(src).get(i),cur_val,vis);
			}
			if(max_value<cur_val){
				max_value=cur_val;
			}
			cur_val=0;
		}
	}
	public static ArrayList<Integer> pf(int n){
		ArrayList<Integer> arr = new ArrayList<>();
		boolean flag=false;
		while(n%2==0){
			flag=true;
			n/=2;
		}
		if(flag){
			arr.add(2);
		}
		for(int i=3;i<=Math.sqrt(n);i++){
			if(n%i==0){
				arr.add(i);
				while(n%i==0){
					n/=i;
				}
			}
		}
		if(n>1){
			arr.add(n);
		}
		return arr;
	}
	static int gcd(int a, int b){
		if(b==0){
			return a;
		}
		else{
			return gcd(b,a%b);
		}
	}
	static boolean function(int n, int i, int[] arr, int sum){
		if(sum==0){
			return true;
		}
		if(i==n && sum!=0){
			return false;
		}
		if(sum<arr[i]){
			return function(n,i+1,arr,sum);
		}
		else{
			return function(n,i+1,arr,sum-arr[i]) || function(n,i+1,arr,sum);
		}
	}
	public static long fact( long n, long mod){
		long res =1;
		for(int i=1;i<=n;i++){
			res%=mod;
			i%=mod;
			res=(res*i)%mod;
		}
		return res;
	}

	public static long nCk(long n,long k, long mod){
		return (fact(n,mod)%mod*modular(fact(k,mod),mod-2,mod)%mod*modular(fact(n-k,mod),mod-2,mod)%mod)%mod;
	}

	public static long modular(long n, long e, long mod){
		long res = 1;
		n%=mod;
		if (n == 0) return 0;
		while(e>0){
			if((e&1)==1){
				res=(res*n)%mod;
			}
			e=e>>1;
			n=(n*n)%mod;
		}
		return res;
	}

	static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
 
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}