A sequence of non-negative integers a_1, a_2, ..., a_n is called growing if for all i from 1 to n - 1 all ones (of binary representation) in a_i are in the places of ones (of binary representation) in a_{i + 1} (in other words, a_i \:\&\: a_{i + 1} = a_i, where \& denotes [bitwise AND](http://tiny.cc/xpy9uz)). If n = 1 then the sequence is considered growing as well.

For example, the following four sequences are growing: 

  * [2, 3, 15, 175] — in binary it's [10_2, 11_2, 1111_2, 10101111_2]; 
  * [5] — in binary it's [101_2]; 
  * [1, 3, 7, 15] — in binary it's [1_2, 11_2, 111_2, 1111_2]; 
  * [0, 0, 0] — in binary it's [0_2, 0_2, 0_2]. 



The following three sequences are non-growing: 

  * [3, 4, 5] — in binary it's [11_2, 100_2, 101_2]; 
  * [5, 4, 3] — in binary it's [101_2, 100_2, 011_2]; 
  * [1, 2, 4, 8] — in binary it's [0001_2, 0010_2, 0100_2, 1000_2]. 



Consider two sequences of non-negative integers x_1, x_2, ..., x_n and y_1, y_2, ..., y_n. Let's call this pair of sequences co-growing if the sequence x_1 ⊕ y_1, x_2 ⊕ y_2, ..., x_n ⊕ y_n is growing where ⊕ denotes [bitwise XOR](http://tiny.cc/bry9uz).

You are given a sequence of integers x_1, x_2, ..., x_n. Find the lexicographically minimal sequence y_1, y_2, ..., y_n such that sequences x_i and y_i are co-growing.

The sequence a_1, a_2, ..., a_n is lexicographically smaller than the sequence b_1, b_2, ..., b_n if there exists 1 ≤ k ≤ n such that a_i = b_i for any 1 ≤ i < k but a_k < b_k.

Input

The first line contains an integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains an integer n (1 ≤ n ≤ 2 ⋅ 10^5) — length of the sequence x_i.

The second line contains n integers x_1, x_2, ..., x_n (0 ≤ x_i < 2^{30}) — elements of the sequence x_i.

It is guaranteed that the sum of n overall all test cases doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print n integers y_1, y_2, ..., y_n (0 ≤ y_i < 2^{30}) — lexicographically minimal sequence such that such that it's co-growing with given sequence x_i.

Example

Input


5
4
1 3 7 15
4
1 2 4 8
5
1 2 3 4 5
4
11 13 15 1
1
0


Output


0 0 0 0 
0 1 3 7 
0 1 0 3 2 
0 2 0 14 
0 

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
public class asis
{		
	 static class Reader {
		 
	        final private int BUFFER_SIZE = 1 << 16;
	        private DataInputStream din;
	        private byte[] buffer;
	        private int bufferPointer, bytesRead;
	 
	        public Reader()
	        {
	            din = new DataInputStream(System.in);
	            buffer = new byte[BUFFER_SIZE];
	            bufferPointer = bytesRead = 0;
	        }
	 
	        public Reader(String file_name) throws IOException
	        {
	            din = new DataInputStream(
	                new FileInputStream(file_name));
	            buffer = new byte[BUFFER_SIZE];
	            bufferPointer = bytesRead = 0;
	        }
	 
	        public String readLine() throws IOException
	        {
	            byte[] buf = new byte[64]; // line length
	            int cnt = 0, c;
	            while ((c = read()) != -1) {
	                if (c == '\n') {
	                    if (cnt != 0) {
	                        break;
	                    }
	                    else {
	                        continue;
	                    }
	                }
	                buf[cnt++] = (byte)c;
	            }
	            return new String(buf, 0, cnt);
	        }
	 
	        public int nextInt() throws IOException
	        {
	            int ret = 0;
	            byte c = read();
	            while (c <= ' ') {
	                c = read();
	            }
	            boolean neg = (c == '-');
	            if (neg)
	                c = read();
	            do {
	                ret = ret * 10 + c - '0';
	            } while ((c = read()) >= '0' && c <= '9');
	 
	            if (neg)
	                return -ret;
	            return ret;
	        }
	 
	        public long nextLong() throws IOException
	        {
	            long ret = 0;
	            byte c = read();
	            while (c <= ' ')
	                c = read();
	            boolean neg = (c == '-');
	            if (neg)
	                c = read();
	            do {
	                ret = ret * 10 + c - '0';
	            } while ((c = read()) >= '0' && c <= '9');
	            if (neg)
	                return -ret;
	            return ret;
	        }
	 
	        public double nextDouble() throws IOException
	        {
	            double ret = 0, div = 1;
	            byte c = read();
	            while (c <= ' ')
	                c = read();
	            boolean neg = (c == '-');
	            if (neg)
	                c = read();
	 
	            do {
	                ret = ret * 10 + c - '0';
	            } while ((c = read()) >= '0' && c <= '9');
	 
	            if (c == '.') {
	                while ((c = read()) >= '0' && c <= '9') {
	                    ret += (c - '0') / (div *= 10);
	                }
	            }
	 
	            if (neg)
	                return -ret;
	            return ret;
	        }
	 
	        private void fillBuffer() throws IOException
	        {
	            bytesRead = din.read(buffer, bufferPointer = 0,
	                                 BUFFER_SIZE);
	            if (bytesRead == -1)
	                buffer[0] = -1;
	        }
	 
	        private byte read() throws IOException
	        {
	            if (bufferPointer == bytesRead)
	                fillBuffer();
	            return buffer[bufferPointer++];
	        }
	 
	        public void close() throws IOException
	        {
	            if (din == null)
	                return;
	            din.close();
	        }
	 }
	 public static long gcd(long x, long p)
	    {
	        if (x == 0)
	            return p;
	         
	        return gcd(p%x, x);
	    }
	 public static void arrInpInt(int [] arr, int n) throws IOException
	 {
		 Reader reader = new Reader();
		 for(int i=0;i<n;i++)
	   		{
	   			arr[i]=reader.nextInt();	
	   		}
	 }
	 public static void arrInpLong(long [] arr, int n) throws IOException
	 {
		 Reader reader = new Reader();
		 for(int i=0;i<n;i++)
	   		{
	   			arr[i]=reader.nextLong();	
	   		}
	 }
	 public static void printArr(int[] arr)
	 {
		 for(int i=0;i<arr.length;i++)
		 {
			 System.out.print(arr[i]+" ");
		 }
		 System.out.println();
	 }
	 public static int[] decSort(int[] arr)
	 {
		  int[] arr1 = Arrays.stream(arr).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray();	
		  return arr1;
	 }
	 
	public static int binarySearch(int arr[], int l, int r, int x)
	    {
	        if (r >= l) {
	            int mid = l + (r - l) / 2;
	            if (arr[mid] == x)
	                return mid;
	            if (arr[mid] > x)
	                return binarySearch(arr, l, mid - 1, x);
	            return binarySearch(arr, mid + 1, r, x);
	        }
	        return -1;
	    }
	//if present - return the first occurrence of the no
	//not present- return the index of next greater value 
	//if greater than all the values return N(taking high=N-1)
	//if smaller than all the values return 0(taking low =0)
	static int lower_bound(int arr[], int low,
	             int high, int X)
	{

	 if (low > high) {
	     return low;
	 }
	 int mid = low + (high - low) / 2;
	 if (arr[mid] >= X) {
	     return lower_bound(arr, low,
	                        mid - 1, X);
	 }

	 return lower_bound(arr, mid + 1,
	                    high, X);
	}
	//if present - return the index of next greater value
	//not present- return the index of next greater value 
	//if greater than all the values return N(taking high=N-1)
	//if smaller than all the values return 0(taking low =0)
	static int upper_bound(int arr[], int low,
	             int high, int X)
	{

	 if (low > high)
	     return low;

	 int mid = low + (high - low) / 2;
	 if (arr[mid] <= X) {
	     return upper_bound(arr, mid + 1,
	                        high, X);
	 }

	 return upper_bound(arr, low,
	                    mid - 1, X);
	}
	
	 public static class Pair  {// comparator with class
		    int x;
		    int y;
		 public Pair(int x, int y)
		    {
		        this.x = x;
		        this.y = y;
		    }
		}

	 private static HashMap sortValues(HashMap<Integer,ArrayList<Integer>> map)   
	 {   
	 List list = new LinkedList(map.entrySet());    
	 Collections.sort(list, new Comparator()   
	 {  
	 public int compare(Object o1, Object o2)   
	 {  
	 return ((Comparable) ((Map.Entry) (o1)).getValue()).compareTo(((Map.Entry) (o2)).getValue());  
	 }  
	 });  
	 //copying the sorted list in HashMap to preserve the iteration order  
	 HashMap sortedHashMap = new LinkedHashMap();  
	 for (Iterator it = list.iterator(); it.hasNext();)   
	 {  
	  Map.Entry entry = (Map.Entry) it.next();  
	 sortedHashMap.put(entry.getKey(), entry.getValue());  
	 }   
	 return sortedHashMap;  
	 }  
	public static void main(String args[]) throws NumberFormatException, IOException ,java.lang.Exception
	{
		
		Reader reader = new Reader();
		//Scanner reader=new Scanner(System.in);
		//BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
		//BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		//int cases=Integer.parseInt(br.readLine());
		//int cases=1;
		int cases=reader.nextInt();
		
   	while (cases-->0){
 
   		int N=reader.nextInt();
   		//int K=reader.nextInt();
   		//int N=Integer.parseInt(br.readLine());
   		//String[] first=br.readLine().split(" ");
   		//int X=Integer.parseInt(first[0]);
   		//int Y=Integer.parseInt(first[1]);
   		//int X=reader.nextInt();
   		//int Y=reader.nextInt();
   		//String str=br.readLine();
   		//int max=Integer.MIN_VALUE;
   		//int min=Integer.MAX_VALUE;
   		//HashMap<Integer,ArrayList<Integer>> map=new HashMap<Integer,ArrayList<Integer>>();
   		//HashSet<Integer> map=new HashSet<Integer>();
   		int [] arr=new int[N];
   		int [] arr1=new int[N];
   		//long[]arr=new long[N];
   		//arrInpInt(arr,N);
   		//arrInpLong(arr,N);
   		//int[] arr1=decSort(arr);
   		//printArr(arr1);
   	 for(int i=0;i<N;i++)
		{
			arr[i]=reader.nextInt();	
		}
   		arr1[0]=0;
   		int prev=arr[0];
   		for(int i=1;i<N;i++)
   		{
   			int curr=arr[i];
   			int ne=0;
   			int p=0;
   			//if(curr&prev==1)
   			while(prev >0)
   			{
   				if((prev&1)==1)
   				{
   					if((curr&1)==0)
   					{
   						ne=ne+(1<<p);
   					}
   					
   				}
   				curr=curr>>1;
   				prev=prev>>1;
   				p++;
   				
   					
   			}
   			arr1[i]=ne;
   			prev=(arr[i]^ne);
   			//System.out.println(prev+"  "+arr[i]+"  "+ne);
   		}
//   		5
//   		4
//   		1 3 7 15
//   		4
//   		1 2 4 8
//   		5
//   		1 2 3 4 5
//   		4
//   		11 13 15 1
//   		1
//   		0
   		printArr(arr1);
     
   		
   		}
   		
   	
   		
}
}

