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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
public class Main{
    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

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

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

        int[] nextArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }
        long[] nextArray(long n) {
            long[] a = new long[(int) n];
            for (int i = 0; i < n; i++) a[i] = nextLong();
            return a;
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
    static class FastWriter extends PrintWriter {
        FastWriter(){
            super(System.out);
        }
        void println(int[] array) {
            for(int i=0; i<array.length; i++) {
                print(array[i]+" ");
            }
            println();
        }
        void println(long [] array) {
            for(int i=0; i<array.length; i++) {
                print(array[i]+" ");
            }
            println();
        }
    }
    static int MOD=998244353;
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner();
        FastWriter out = new FastWriter();
        int t=in.nextInt();
        //int t=1;
        while (t-->0){
            int n=in.nextInt();
            int[] ar1=in.nextArray(n);
            int[] ar2=new int[n];
            ar2[0]=0;
            for (int i = 1; i < n; i++) {
                int num=ar1[i-1]^ar2[i-1];
                if((num&ar1[i])==num){
                    ar2[i]=0;
                }else {
                    StringBuilder ss= new StringBuilder();
                    String s1=Integer.toBinaryString(num);
                    String s2=Integer.toBinaryString(ar1[i]);
                    int l1=s1.length(),l2=s2.length();
                    if(l2<l1){
                        for (int j = 0; j < l1 - l2; j++) {
                            s2="0"+s2;
                        }
                        l2=l1;
                    }
                    for (int j =0; j <l1; j++){
                        if(s1.charAt(j)=='1'&&s2.charAt(l2-l1+j)=='0'){
                            ss.append("1");
                        }else {
                            ss.append("0");
                        }
                    }
                    ar2[i]=Integer.parseInt(ss.toString(),2);
                }
            }
            out.println(ar2);
        }
        out.close();
    }
    //Arrays.sort(a, (o1, o2) -> (o1[0] - o2[0]));
    static int subarray_lessthan_k(int[] A,int n,int k){
        int s=0,e=0,sum=0,cnt=0;
        while(e<n){
            sum+=A[e];
            while(s<=e&&sum>k){
                sum-=A[s++];
            }
            cnt+=e-s+1;
            e++;
        }
        return cnt;
    }
    static int totalPrimeFactors(int n) {
        int cnt=0;
        while (n%2==0) {
            cnt++;
            n /= 2;
        }
        int num= (int) Math.sqrt(n);
        for (int i = 3; i <= num; i+= 2) {
            while (n%i == 0) {
                cnt++;
                n /= i;
                num=(int)Math.sqrt(n);
            }
        }
        if (n > 2){
            cnt++;
        }
        return cnt;
    }
    static char get(int i){
        return (char)(i+'a');
    }
    static boolean distinct(int num){
        HashSet<Integer> set=new HashSet<>();
        int len=String.valueOf(num).length();
        while (num!=0){
            set.add(num%10);
            num/=10;
        }
        return set.size()==len;
    }
    static int maxSubArraySum(int a[],int st,int en) {
        int max_s = Integer.MIN_VALUE, max_e = 0,ind=0,ind1=1;
        for (int i = st; i <= en; i++) {
            max_e+= a[i];
            if (max_s < max_e){
                max_s = max_e;
                ind=ind1;
            }
            if (max_e < 0){
                max_e = 0;
                ind1=i+1;
            }
        }
        if(st==0){
            return max_s;
        }
        if(ind==1){
            return a[0]+2*max_s;
        }else {
            return 2*max_s+maxSubArraySum(a,0,ind-1);
        }
        //return max_s;
    }
    static void segmentedSieve(ArrayList<Integer> res,int low, int high) {
        if(low < 2){
            low = 2;
        }
        ArrayList<Integer> prime = new ArrayList<>();
        simpleSieve(high, prime);
        boolean[] mark = new boolean[high - low + 1];
        for (int i = 0; i < mark.length; i++){
            mark[i] = true;
        }
        for (int i = 0; i < prime.size(); i++) {
            int loLim = (low / prime.get(i)) * prime.get(i);
            if (loLim < low){
                loLim += prime.get(i);
            }
            if (loLim == prime.get(i)){
                loLim += prime.get(i);
            }
            for (int j = loLim; j <= high; j += prime.get(i)) {
                mark[j - low] = false;
            }
        }
        for (int i = low; i <= high; i++) {
            if (mark[i - low]){
                res.add(i);
            }
        }
    }
    static void simpleSieve(int limit, ArrayList<Integer> prime) {
        int bound = (int)Math.sqrt(limit);
        boolean[] mark = new boolean[bound + 1];
        for (int i = 0; i <= bound; i++){
            mark[i] = true;
        }
        for (int i = 2; i * i <= bound; i++) {
            if (mark[i]) {
                for (int j = i * i; j <= bound; j += i){
                    mark[j] = false;
                }
            }
        }
        for (int i = 2; i <= bound; i++) {
            if (mark[i]){
                prime.add(i);
            }
        }
    }
    static int highestPowerOf2(int n) {
        if (n < 1){ return 0; }
        int res = 1;
        for (int i = 0; i < 8 * Integer.BYTES; i++) {
            int curr = 1 << i;
            if (curr > n){ break; }
            res = curr;
        }
        return res;
    }
    static int reduceFraction(int x, int y) {
        int d= gcd(x, y);
        return x/d+y/d;
    }
    static boolean subset(int[] ar,int n,int sum){
        if(sum==0){
            return true;
        }
        if(n<0||sum<0){
            return false;
        }
        return subset(ar,n-1,sum)||subset(ar,n-1,sum-ar[n]);
    }
    static boolean isPrime(int n){
        if(n<=1) return false;
        for(int i = 2;i<=Math.sqrt(n);i++){
            if (n % i == 0) return false;
        }
        return true;
    }
    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    static long lcm(long a, long b) {
        return (a * b) / gcd(a, b);
    }
    static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
    static boolean isPowerOfTwo(long n) {
        if(n==0){
            return false;
        }
        while (n%2==0){
            n/=2;
        }
        return n==1;
    }
    static boolean isPerfectSquare(int x){
        if (x >= 0) {
            int sr = (int)Math.sqrt(x);
            return ((sr * sr) == x);
        }
        return false;
    }
    static int lower_bound(int[] arr, int x) {
        int low_limit = 0, high_limit = arr.length, mid;
        while (low_limit < high_limit) {
            mid = (low_limit + high_limit) / 2;
            if (arr[mid] >= x){
                high_limit = mid;
            }else{
                low_limit = mid + 1;
            }
        }
        return low_limit;
    }
    static int upper_bound(int[] arr, int x) {
        int low_limit = 0, high_limit = arr.length, mid;
        while (low_limit < high_limit) {
            mid = (low_limit + high_limit) / 2;
            if (arr[mid] > x){
                high_limit = mid;
            }else{
                low_limit = mid + 1;
            }
        }
        return low_limit;
    }
    static int binarySearch(int[] ar,int n,int num){
        int low=0,high=n-1;
        while (low<=high){
            int mid=(low+high)/2;
            if(ar[mid]==num){
                return mid;
            }else if(ar[mid]>num){
                high=mid-1;
            }else {
                low=mid+1;
            }
        }
        return -1;
    }
    static int fib(int n) {
        long F[][] = new long[][]{{1,1},{1,0}};
        if (n == 0){
            return 0;
        }
        power(F, n-1);
        return (int)F[0][0];
    }
    static void multiply(long F[][], long M[][]) {
        long x =  (F[0][0]*M[0][0])%1000000007 + (F[0][1]*M[1][0])%1000000007;
        long y =  (F[0][0]*M[0][1])%1000000007 + (F[0][1]*M[1][1])%1000000007;
        long z =  (F[1][0]*M[0][0])%1000000007 + (F[1][1]*M[1][0])%1000000007;
        long w =  (F[1][0]*M[0][1])%1000000007 + (F[1][1]*M[1][1])%1000000007;
        F[0][0] = x%1000000007;
        F[0][1] = y%1000000007;
        F[1][0] = z%1000000007;
        F[1][1] = w%1000000007;
    }
    static void power(long F[][], int n) {
        if( n == 0 || n == 1){
            return;
        }
        long M[][] = new long[][]{{1,1},{1,0}};
        power(F, n/2);
        multiply(F, F);
        if (n%2 != 0){
            multiply(F, M);
        }
    }
}