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.*;
import java.lang.*;

public class Main {
    //input
    static out op = new out();
    static inp ip = new inp();
    static FastReader sc = new FastReader();
    static BufferedWriter output = new BufferedWriter( 
        new OutputStreamWriter(System.out));
    static long inf = (long)1e9+7;
   
    //HashMap<Integer,Integer> map = new HashMap<>();

    // for(int i=0;i<n;i++){
            
    // }
    static long mod = (long)1e9+7;
    static void sol() throws Exception{
       int n = ip.in();
       long[] arr = new long[n];
       
       for(int i=0;i<n;i++){
          arr[i] = ip.in();
       }
       
       ArrayList<Integer> ans = new ArrayList<>();
       HashSet<Integer> bt = new HashSet<>();
       StringBuffer sb = new StringBuffer();
       
       int b=0;
       long val = 0;
       long a0 = arr[0];
       while(a0>0){
          if((a0&1) != 0){
             bt.add(b);
          }
          a0 = (a0>>1);
          b++;
       }
       sb.append(0+" ");
       for(int i=1;i<n;i++){
          int j=0;
          val = 0;
          long a = arr[i];
          while(a>0){
             if((a&1) == 0){
                if(bt.contains(j))
                  val += ip.pow(2,j);
             }else bt.add(j);
             a = (a>>1);
             j++;
          }
          //op.sbln(b+" "+j);
          
          while(j<b){
             //op.sbln(j);
             if(bt.contains(j))
               val += ip.pow(2,j);
             //op.sbln(val);
             j++;
          }
          b = j;
          sb.append(val+" ");
       }
       op.sbln(sb);
    }
    
    static int gcd(int a,int b){
        if(b==0)
        return a;
        return gcd(b,a%b);
    }

    public static void main(String[] args) throws Exception { 
        int t = ip.in();
      //  HashSet<Long> prime = new HashSet<Long>();
      //  ArrayList<Long> prm = new ArrayList<>(); 
      //  for(long i=2;i<=(long)1e9+7;i++){
      //     if(!prime.contains(i)){
      //        prm.add(i);
      //        for(long j = i*i;j<=(long)1e9+7;j+=i){
      //           prime.add(j);
      //        }
      //     }
      //  }
        
        while(t-- > 0){
             sol();
        }
        op.output.flush();
    }
    static class Node /*implements Comparable<Node>*/{
        int data[] = new int[26];
        int val;
        Node left,right;
        Node(){
            left = null;
            right = null;
        }
        Node(char ch){
            left = null;
            right = null;
        }
    
        // @Override
        // // public int compareTo(Node o) {
        // //     if(this.data == o.data)
        // //     return this.ind - o.ind;
        // //     // TODO Auto-generated method stub
        // //     return o.data - this.data;
        // // }
    }
}


class FastReader 
{ 
    BufferedReader br; 
    StringTokenizer st; 

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

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

    int nextInt() 
    { 
        return Integer.parseInt(next()); 
    } 

    long nextLong() 
    { 
        return Long.parseLong(next()); 
    } 

    double nextDouble() 
    { 
        return Double.parseDouble(next()); 
    } 

    String nextLine() 
    { 
        String str = ""; 
        try
        { 
            str = br.readLine(); 
        } 
        catch (IOException e) 
        { 
            e.printStackTrace(); 
        } 
        return str; 
    }

}
class inp{
    FastReader sc = new FastReader();
    int in(){
        int a = sc.nextInt();
        return a;
    }
    long lin(){
        long a = sc.nextLong();
        return a;
    }
    char cin(){
        char c = sc.next().charAt(0);
        return c;
    }
    char[] cain(){
        char[] a = sc.nextLine().toCharArray();
        return a;
    }
    int[] arrin(int n){
        int [] arr = new int[n];
        for(int i=0;i<n;i++)
            arr[i] = in();

        return arr;
    }
    int[] mm_arr(int[] arr){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i=0;i<arr.length;i++){
            max = Math.max(max,arr[i]);
            min = Math.min(min,arr[i]);
        }
        int ans[] = {max,min};
        return ans;
    }
    int[] srt(int[] arr){
        Arrays.sort(arr);
        return arr;
    }
    long pow(long a,long b){
        if(b == 0)return 1;
        long res = pow(a,b/2);
        //System.out.println(res + " " + b + " " + (b&1));
        if((b&1) == 0)return res*res;
        return a*res*res; 
    }

    boolean[] prime(){
        boolean prime[] = new boolean[100000001];
        Arrays.fill(prime,true);
        for (int p = 2; p * p <= 10000000; p++)
        {
            // If prime[p] is not changed,
            // then it is a prime
            if (prime[p] == true)
            {
                // Update all multiples
                // of p greater than or
                // equal to the square of it
                // numbers which are multiple
                // of p and are less than p^2
                // are already been marked.
                for (int i = p * p; i <= 10000000; i += p)
                    prime[i] = false;
            }
        }
        return prime;
    }
}
class out{
    BufferedWriter output = new BufferedWriter( 
        new OutputStreamWriter(System.out)); 

    void sb(String s) throws IOException {
        output.write(s);
    }
    void sbln(Object s) throws IOException {
        output.write(s+"\n");
    }
    void yes() throws IOException{
        output.write("YES\n");
    }
    void no() throws IOException{
        output.write("NO\n");
    }
}
