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.io.*;
import java.lang.reflect.Array;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;

public class copy {
    static long ans;
    static long mod=1000000007;
    static ArrayList<Integer> answer;
    static int time=0;
    static boolean status;
    public static long[] inv(long[] arr,int l,int r)
    {
        if(l>r)
            return null;

        if(l==r)
        {
            long[] sum=new long[1];
            sum[0]=arr[l];
            return sum;
        }

        int mid=(l+r)/2;
        long[] sum1=inv(arr,l,mid);
        long[] sum2=inv(arr,mid+1,r);
        long[] sum3=merge(arr,l,mid,r,sum1,sum2);
        return sum3;
    }

    public static long[] merge(long[] arr,int l,int mid,int r,long[] sum1,long[] sum2)
    {
        //System.out.println(l+" "+mid+" "+r+" "+ans);
        int N=mid-l+1;
        int M=r-mid;
        long[] arr1=new long[N];
        long[] arr2=new long[N];
        long[] mer=new long[N+M];
        for(int i=0;i<N;i++)
            arr1[i]=arr[l+i];
        for(int i=0;i<M;i++)
            arr2[i]=arr[mid+1+i];
        int k=0;
        int c=0,d=0;
        while(c<N && d<M)
        {
            if(arr1[c]<=arr2[d])
            {
                mer[k++]=arr1[c++];
            }
            else
            {
//                System.out.println(arr2[d]+" hello "+arr1[c]);
//                System.out.println(sum[mid]+" LAUDE "+sum[c]+" "+arr1[c]);
                ans+=sum1[N-1]-sum1[c]+arr1[c];

                mer[k++]=arr2[d++];
            }
        }

        while(c<N)
            mer[k++]=arr1[c++];

        while(d<M)
            mer[k++]=arr2[d++];
        long s=0;
        long[] sum=new long[N+M];
        //System.out.println("SUM");
        for(int i=0;i<N+M;i++)
        {
            s+=mer[i];
            //System.out.print(s+" ");
            sum[i]=s;
        }
        //System.out.println();
        for(int i=0;i<mer.length;i++)
        {
            arr[l+i]=mer[i];
        }
        //System.out.println("ANSWER "+ans);
        return sum;
    }
    public static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public static int bin(ArrayList<Integer> arr,int check)
    {
        if(check<=arr.get(0))
            return 0;
        if(check>arr.get(arr.size()-1))
            return arr.size();
        int l=0;
        int r=arr.size()-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(arr.get(mid)>=check)
            {
                if(mid-1>=0 && arr.get(mid-1)>=check)
                    r=mid-1;
                else
                    return mid;
            }
            else
                l=mid+1;
        }

        return -1;
    }

    public static void dfs(ArrayList<ArrayList<Integer>> arr,int x,int parent,int even,int odd,int level,int[] initial,int[] fin)
    {
        if(level%2==0)
        {
            if((initial[x]+even)%2!=fin[x])
            {
                ++ans;
                even+=1;
                answer.add(x+1);
            }
        }
        else
        {
            if((initial[x]+odd)%2!=fin[x])
            {
                ++ans;
                odd+=1;
                answer.add(x+1);
            }
        }

        for(int i:arr.get(x))
        {
            if(i!=parent)
            {
                dfs(arr,i,x,even,odd,level+1,initial,fin);
            }
        }
    }

    public static long dp(long[] dp,int floor)
    {
        //System.out.println(floor);
        if(dp[floor]!=-1)
            return dp[floor];
        if(floor==0)
            return 1;
        if(floor==1)
            return 1;

        long left=dp(dp,floor-1);
        long right=dp(dp,floor-2);

        dp[floor]=(left%mod+right%mod)%mod;
        return dp[floor];
    }
    public static void dfs(ArrayList<ArrayList<Integer>> arr,ArrayList<ArrayList<Integer>> weights,int x,boolean[] visited,int[] dist,int d)
    {

        dist[x]=d;
        visited[x]=true;
        //System.out.println(x);
        for(int i=0;i<arr.get(x).size();i++)
        {
            if(!visited[arr.get(x).get(i)])
            {
                dfs(arr,weights,arr.get(x).get(i),visited,dist,d+weights.get(x).get(i));
            }
            else
            {
                if(dist[arr.get(x).get(i)]!=d+weights.get(x).get(i))
                    status=false;
            }
        }

    }
    static int diff=Integer.MAX_VALUE;
    public static void check(long[][] max,long[][] min,int x,int y,int M)
    {
        for(int i=0;i<M;i++)
        {
            if(max[x+1][i]==-1)
                check(max,min,x+1,i,M);
        }

        for(int i=0;i<M;i++)
        {

        }
    }

    public static void main(String[] args)throws IOException
    {
        Reader.init(System.in);
        BufferedWriter output=new BufferedWriter(new OutputStreamWriter(System.out));
        int T=Reader.nextInt();
        for(int m=1;m<=T;m++)
        {
            int N=Reader.nextInt();
            ArrayList<Integer> arr=new ArrayList<>();
            for(int i=0;i<N;i++)
                arr.add(Reader.nextInt());
            int xor=0;
            output.write(0+" ");
            for(int i=0;i<N-1;i++)
            {
                int x=arr.get(i)^xor;
                int log=(int)(Math.log(x)/Math.log(2));
                int num=(int)Math.pow(2,log)-1;
                //System.out.println(num);
                String s="";
                int x1=x;

                int co=arr.get(i+1);
                int co1=co;
                while(co>0 || x1>0)
                {
                    if(co%2!=0)
                        s="1"+s;
                    else
                    {
                        if(x1%2==0)
                            s="0"+s;
                        else
                            s="1"+s;
                    }
                    x1=x1>>1;
                    co=co>>1;
                }
//                if(i==2)
//                {
//                    System.out.println(x+" hello "+co);
//                    System.out.println(x&co);
//                }

//                if((co&x)==x)
//                {
//                    output.write(0+" ");
//                    xor=0;
//                    continue;
//                }
//                while(num>0)
//                {
//                    //System.out.println(num+" "+co);
//                    if(num%2==0 && co%2==0)
//                        s="0"+s;
//                    else if(num%2==0 && co%2!=0)
//                        s="1"+s;
//                    else if(num%2!=0 && co%2==0)
//                    {
//                        s="1"+s;
//                    }
//                    else
//                        s="0"+s;
//                    num=num>>1;
//                    co=co>>1;
//                }
                if(s.equals(""))
                {
                    s+="0";

                }
                //System.out.println(s+" "+co1);
                xor=co1^Integer.parseInt(s,2);
                output.write(xor+" ");

            }

            output.write("\n");

        }
        output.flush();
    }
}

class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

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

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

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

class cp
{
    int l,r;
    cp(int a,int b)
    {
        this.l=a;
        this.r=b;
    }
}

class sort_cp_l implements Comparator<cp>
{
    public int compare(cp o1,cp o2)
    {
        if(o1.l<o2.l)
            return -1;
        else if(o2.l<o1.l)
            return 1;
        else
            return 0;
    }
}

class sort_cp_middle implements Comparator<cp>
{
    public int compare(cp o1,cp o2)
    {
        return o2.r-o1.r;
    }
}

class sort_cp_r implements Comparator<cp>
{
    public int compare(cp o1,cp o2)
    {
        return o1.r-o2.r;
    }
}