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 
//template

import java.util.*;
import java.io.*;
public class Codechef{
    //SOLUTION BEGIN
    class pair{
    	int x,y;
    	pair(int f,int s){
    		x=f;
    		y=s;
    	}
    }
    void pre() throws Exception{}
    int get(int a,int b) {
    	int ans=0;
    	int i=0;
    	while(a>0 ) {
    		if((a&1)==1 && (b&1)==0){
    			
    		
    			ans+=(int)Math.pow(2, i);
    		}
    		a>>=1;b>>=1;
    		i++;
    	}
    	
    	return ans;
    }
   int num1(int a) {
	   double i=(Math.log(a)/Math.log(2));
	   
	   return (int)(i+1);
   }
    void solve(int TC) throws Exception{
    	int n=ni();
    	int a=ni();
    	p("0 ");
    	
    	int x;
    	for(int i=1;i<n;i++) {
//    		int b=ni();
//    		int temp=a;
//    		if((a&b)==a) {
//    			a=b;
//    			p("0 ");
//    			continue;
//    		}
//    		x=(a<<1)+1;
//    		a=x;
//    		x=x^b;
//    		int y=temp^b;
//    		if(y<=x) {
//    			a=temp;
//    			x=y;
//    		}
//    		p(x+" ");
    		int b=ni();
    		if((a&b)==a) {
    			a=b;
    			p("0 ");
    			continue;
    		}
    		int temp=a;
    		
    		int y=get(temp,b);
    		a=b^y;
    		p(y+" ");
    		
    		
    	}
    	pn(" ");
    }
    
    //SOLUTION END
    
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new Codechef().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

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

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
	    
	
	final static int N=1000000007;
	static long expo(long base, long exp)
	{
	    if (exp == 0)
	        return 1;
	
	    if (exp == 1)
	        return base % N;
	
	    long t = expo(base, exp / 2);
	    t = (t * t) % N;
	
	    // if exponent is even value
	    if (exp % 2 == 0)
	        return t;
	
	    // if exponent is odd value
	    else
	        return ((base % N) * t) % N;
	}
    
}