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.io.*;
 
public class D_Co_growing_Sequence{
    public static void main(String[] args) {
        FastScanner s= new FastScanner();
        StringBuilder res = new StringBuilder();
        int t=s.nextInt();
        int p=0;
        while(p<t){
        int n=s.nextInt();
        int array[]= new int[n];
        for(int i=0;i<n;i++){
            array[i]=s.nextInt();
        }
        if(n==1){
            res.append("0\n");
            p++;
            continue;
        }
        ArrayList<Integer> ans = new ArrayList<Integer>();
        ans.add(0);
        ArrayList<Integer> prev = new ArrayList<Integer>();
        long num=array[0];
        while(num>0){
            int dig= (int)(num&1);
            prev.add(dig);
            num=num>>1;
        }
        for(int i=1;i<n;i++){
            int num2=array[i];
            ArrayList<Integer> curr = new ArrayList<Integer>();
            while(num2>0){
                int dig= (int)(num2&1);
                curr.add(dig);
                num2=num2>>1;
            }
            int parray[]= new int[32];
            int size=curr.size();
            for(int j=0;j<prev.size();j++){
            
                if(prev.get(j)==1){
                     if(size<=j){
                         parray[j]=1;
                         continue;
                     }
                     else{
                         if(curr.get(j)==0){
                             parray[j]=1;
                         }
                     }
                }
            }
          
            int yo=0;
            for(int j=0;j<parray.length;j++){
               
               if(array[i]==0){
                   curr.add(parray[j]);
               }
                if(parray[j]==1){
                    int kk=(int)Math.pow(2,j);
                    yo+=kk;
                    if(array[i]==0){
                       
                        continue;
                    }
                    if(j<curr.size()){
                    curr.set(j,1);
                    }
                    else{
                        int counter=curr.size();
                        while(true){
                            if(counter==j){
                                curr.add(1);
                                break;
                            }
                            else{
                                curr.add(0);
                                counter++;;
                            }
                        }
                    }
                }
                
            }
         
            ans.add(yo);
            prev=curr;
 
        }
        for(int i=0;i<ans.size();i++){
            res.append(ans.get(i)+" ");
        }
        res.append("\n");
        p++;
    }
    System.out.println(res);
 
    }
    static class FastScanner {
		BufferedReader br;
		StringTokenizer st;
 
		public FastScanner(String s) {
			try {
				br = new BufferedReader(new FileReader(s));
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
 
		public FastScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String nextToken() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(nextToken());
		}
 
		long nextLong() {
			return Long.parseLong(nextToken());
		}
 
		double nextDouble() {
			return Double.parseDouble(nextToken());
		}
	}
 
 
 
 
}