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:
// package Jobeel;
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.*;
import java.util.Map.*;

public class codeforces {
	
      public static void main(String [] args) throws IOException, InterruptedException {
	    InputReader sc=new InputReader(System.in);
	    int t=sc.nextInt();
	    while(t-->0) {
	    	int x=sc.nextInt();
	    	int [] arr=new int [x];
	    	arr[0]=sc.nextInt();
	    	long sum=arr[0];
	    	long xor=sum;
	    	for(int i=1;i<x;i++) {
	    		arr[i]=sc.nextInt();
	    		sum+=arr[i]; xor=xor^arr[i]; 
	    	}
	    	long b=sum+xor;
	        if(xor ==0 && b==0) pw.println(0+"\n");
	        else if(xor ==0) pw.println(1+"\n"+b);
	        else if (b==0) pw.println(1+"\n"+xor);
	        else pw.println(2+"\n"+b+" "+xor);
	    }
	    pw.println();
	    pw.flush();
		pw.close();
	}
    static int [] size,arr;
  	static int inv;
  	static long M=(long)1e9+9,P=999983;
  	static HashSet<StringBuilder> set_1;
  	static TreeSet<Long> set; 
  	public static long computeHash(String x) {
  		int p=31,m=(int)1e9+9;
  		char [] ch=x.toCharArray();
  		long hash_value=0;
  		long pow =1 ;
  		for(char c: ch) {
  			hash_value=(hash_value+(c-'a'+1)*pow)%m;
  			pow=(pow*p)%m;
  		}
  		return hash_value;
  	}
  	public static ArrayList<Integer> rabin_Karp(String s,String t){
  		int p=31,m=(int)1e9+9;
  		int S=s.length(),T=t.length();
  		long [] p_pow =new long[Math.max(S, T)];
  		p_pow[0]=1;
  		for(int i=1;i<p_pow.length;i++) p_pow[i]=(p_pow[i-1]*p)%m;
  	    long [] hash_t=new long[T+1];
  	    for(int i=0;i<T;i++) 
  	    	hash_t[i+1]=(hash_t[i]+(t.charAt(i)-'a'+1)*p_pow[i])%m;
  	   long s_hashvalue=0L;
  	  
  	   for(int i=0;i<S;i++)
  		   s_hashvalue=(s_hashvalue+((long)(s.charAt(i)-'a'+1))*p_pow[i])%m;
  	   ArrayList<Integer> list=new ArrayList<>();
  	   for(int i=0;i+S-1<T;i++) {
  		   long cur_h=(hash_t[i+S]+m-hash_t[i])%m;
  		   System.out.println(cur_h+" "+s_hashvalue);
  		   if(cur_h==(s_hashvalue*p_pow[i])%m) list.add(i);
  	   }
  	   return list;
  	}
      static void solveBruteForece(int index , int mask) {
  		if(index==arr.length) {
  			long sum=0;
  			for(int i=0;i<arr.length;i++) {
  				if((mask & 1<<i)!=0) sum+=arr[i];
  				
  			}
  			set.add(sum);
  			return;
  		}
  		solveBruteForece(index+1,mask | 1<<index);
  		solveBruteForece(index+1,mask);
  	}
  	public static int find(int i) {
  		if(arr[i]==i) return i;
  		else {
  			int result=find(arr[i]);
  			arr[i]=result;
  			return result;
  		}
  	}
  public static void union(int u,int v) {
  		int root_u=find(u);
  		int root_v=find(v);
  		if (root_u==root_v) return;
  		else if(size[root_u]>size[root_v]) {
  			size[root_u]+=size[root_v];
  			arr[root_v]=root_u;
  		}else  {
  			size[root_v]+=size[root_u];
  			arr[root_u]=root_v;
  		}
  	}
      static int search(int x,pair [] arr) {
      	int low=0,high=arr.length-1,ans=-1;
      	while(low<=high) {
      		int mid=(low+high)>>1;
      	    if(arr[mid].x>=x) {ans=mid; high=mid-1;}
      	    else low=mid+1;
      	}
      	return ans;
      }
     static  long gcd(long a, long b) 
      { 
          if (b == 0) 
              return a; 
          return gcd(b, a % b);  
            
      } 
     public static long largestDivisor(long n){
  	   long divisor = 0;
  	   long  w=n>>1;
  	   for (int i = 1; i <= w; i++)
  	       if (n % i == 0) 
  	           divisor = i;

  	   return divisor; 
  	}
     static void display(char [] ch) {
  	   for(int i=0;i<ch.length;i++) pw.print(ch[i]);
     }
     public static char nextC(char c) {
  	   if(c=='R') return 'G';
  	   else if(c=='G') return 'B';
  	   else return 'R';
     }
     public static boolean helper(int [] a,int [] b,int x,int m) {
  	   int [] check=new int [a.length];
  	   for(int i=0;i<a.length;i++) check[i]=(x+a[i])%m;
  	   Arrays.parallelSort(check);
  	   for(int i=0;i<a.length;i++) if(check[i]!=b[i]) return false;
  	   return true;
     }
	static class pair implements Comparable<pair>{
		String  name; int x,y ;
		
		
		public pair (int x,int y) {
			this.x=x; this.y=y;
		}
		public int compareTo(pair o) {
			return o.x-x;
		}
		public String toString() {
			return x+" "+y;
		}
	}

	static 	PrintWriter pw=new PrintWriter(System.out);
	public static StringBuilder toString(int [] arr,int l,int r) {
		StringBuilder sb=new StringBuilder();
		for(int i=l;i<=r;i++) sb.append(arr[i]+" ");
		return sb;
	}
	public static StringBuilder toString(long [] arr,int l,int r) {
		StringBuilder sb=new StringBuilder();
		for(int i=l;i<=r;i++) sb.append(arr[i]+" ");
		return sb;
	}
	public static StringBuilder toString(char [] arr,int l,int r) {
		StringBuilder sb=new StringBuilder();
		for(int i=l;i<=r;i++) sb.append(arr[i]);
		return sb;
	}
	static class InputReader  {
		 
		private InputStream in;
		private byte[] buffer = new byte[1024];
		private int curbuf;
		private int lenbuf;
 
		public InputReader(InputStream in) {
			this.in = in;
			this.curbuf = this.lenbuf = 0;
		}
 
		public boolean hasNextByte() {
			if (curbuf >= lenbuf) {
				curbuf = 0;
				try {
					lenbuf = in.read(buffer);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (lenbuf <= 0)
					return false;
			}
			return true;
		}
 
		private int readByte() {
			if (hasNextByte())
				return buffer[curbuf++];
			else
				return -1;
		}
 
		private boolean isSpaceChar(int c) {
			return !(c >= 33 && c <= 126);
		}
 
		private void skip() {
			while (hasNextByte() && isSpaceChar(buffer[curbuf]))
				curbuf++;
		}
 
		public boolean hasNext() {
			skip();
			return hasNextByte();
		}
 
		public String next() {
			if (!hasNext())
				throw new NoSuchElementException();
			StringBuilder sb = new StringBuilder();
			int b = readByte();
			while (!isSpaceChar(b)) {
				sb.appendCodePoint(b);
				b = readByte();
			}
			return sb.toString();
		}
 
		public int nextInt() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}
 
		public long nextLong() {
			if (!hasNext())
				throw new NoSuchElementException();
			int c = readByte();
			while (isSpaceChar(c))
				c = readByte();
			boolean minus = false;
			if (c == '-') {
				minus = true;
				c = readByte();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = res * 10 + c - '0';
				c = readByte();
			} while (!isSpaceChar(c));
			return (minus) ? -res : res;
		}
 
		public double nextDouble() {
			return Double.parseDouble(next());
		}
 
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
 
		public long[] nextLongArray(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}
 
	}

	}