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 
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		FastNum in = new FastNum(System.in);
		Reader sc = new Reader();
		PrintWriter out = new PrintWriter(System.out);
		
		int test = in.nextInt();
		while(test-->0) {
		    int n = in.nextInt();
		    int[] a = new int[n];
		    boolean flag = true;
		    for(int i = 0; i < n; i++) {
		        a[i] = in.nextInt();
		        if(i != 0) {
		            if(a[i-1] != (a[i] & a[i-1])) {
		                flag = false;
		            }
		        }
		    }
		    int ans[] = new int[n];
		    int t[] = new int[n];
		    t[0] = a[0];
		    if(!flag) {
		        for(int i = 1; i < n; i++) {
		            if(a[i] == t[i-1]){
		                ans[i] = 0;
		                t[i] = a[i] ^ ans[i];
		            }
		            else {
		                ans[i] = Math.min((((a[i]^t[i-1])&a[i])^(a[i]^t[i-1])), t[i-1]);
		                t[i] = a[i] ^ ans[i];
		              //  out.println(ans[i]+ " " + (a[i]^t[i-1]) + " " + t[i-1] + " " + a[i]);
		            }
		        }
		    }
		    
		    for(int i : ans) out.print(i + " ");
		    out.println();
		}
		
		
		
		
		out.flush();
	}
	
    public static long mod=1000000007;
    public static long power(long a, long b) {
	    if(b == 0)
		    return 1;
	    long answer = power(a, b/2)%mod;
	    answer = (answer*answer)%mod;
	    if(b%2!=0)
		    answer = (answer*a)%mod;
	    return answer;
    }
    
    public static void swap(int x, int y) {
        int t = x;
        x = y;
        y = t;
    }
    
    public static long min(long a, long b) {
	    return a<b?a:b;
    }
    
    public static long divide(long a,long b) {
    	return (a%mod*(power(b, mod-2)%mod))%mod;
    }
     
    public static long nCr(long n,long r) {
    	long answer = 1;
    	long k = min(r, n-r);
    	for(long i=0;i<k;i++)	{
    		answer = (answer%mod*(n-i)%mod)%mod;
    		answer = divide(answer, i+1);
    	}
    	return answer%mod;
    }
    
    public static boolean plaindrome(String str) {
        StringBuilder sb=new StringBuilder();
        sb.append(str);
        return (str.equals((sb.reverse()).toString()));
    }
	
	static class Assert {
		static void check(boolean e) {
			if (!e) {
				throw new AssertionError();
			}
		}
	}
	
	static class FastNum implements AutoCloseable {

		InputStream is;
		byte buffer[] = new byte[1 << 16];
		int size = 0;
		int pos = 0;

		FastNum(InputStream is) {
			this.is = is;
		}

		int nextChar() {
			if (pos >= size) {
				try {
					size = is.read(buffer);
				} catch (IOException e) {
					throw new IOError(e);
				}
				pos = 0;
				if (size == -1) {
					return -1;
				}
			}
			Assert.check(pos < size);
			int c = buffer[pos] & 0xFF;
			pos++;
			return c;
		}

		int nextInt() {
			int c = nextChar();
			while (c == ' ' || c == '\r' || c == '\n' || c == '\t') {
				c = nextChar();
			}
			if (c == '-') {
				c = nextChar();
				Assert.check('0' <= c && c <= '9');
				int n = -(c - '0');
				c = nextChar();
				while ('0' <= c && c <= '9') {
					int d = c - '0';
					c = nextChar();
					Assert.check(n > Integer.MIN_VALUE / 10
							|| n == Integer.MIN_VALUE / 10 && d <= -(Integer.MIN_VALUE % 10));
					n = n * 10 - d;
				}
				return n;
			} else {
				Assert.check('0' <= c && c <= '9');
				int n = c - '0';
				c = nextChar();
				while ('0' <= c && c <= '9') {
					int d = c - '0';
					c = nextChar();
					Assert.check(
							n < Integer.MAX_VALUE / 10 || n == Integer.MAX_VALUE / 10 && d <= Integer.MAX_VALUE % 10);
					n = n * 10 + d;
				}
				return n;
			}
		}

		@Override
		public void close() {
		}
	}
	
	
    static class Reader 
    { 
        final private int BUFFER_SIZE = 1 << 16; 
        private DataInputStream din; 
        private byte[] buffer; 
        private int bufferPointer, bytesRead; 
  
        public Reader() 
        { 
            din = new DataInputStream(System.in); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public Reader(String file_name) throws IOException 
        { 
            din = new DataInputStream(new FileInputStream(file_name)); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public String readLine() throws IOException 
        { 
            byte[] buf = new byte[64]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
            { 
                if (c == '\n') 
                    break; 
                buf[cnt++] = (byte) c; 
            } 
            return new String(buf, 0, cnt); 
        } 
  
        public int nextInt() throws IOException 
        { 
            int ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do
            { 
                ret = ret * 10 + c - '0'; 
            }  while ((c = read()) >= '0' && c <= '9'); 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public long nextLong() throws IOException 
        { 
            long ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public double nextDouble() throws IOException 
        { 
            double ret = 0, div = 1; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
  
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
  
            if (c == '.') 
            { 
                while ((c = read()) >= '0' && c <= '9') 
                { 
                    ret += (c - '0') / (div *= 10); 
                } 
            } 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        private void fillBuffer() throws IOException 
        { 
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
            if (bytesRead == -1) 
                buffer[0] = -1; 
        } 
  
        private byte read() throws IOException 
        { 
            if (bufferPointer == bytesRead) 
                fillBuffer(); 
            return buffer[bufferPointer++]; 
        } 
  
        public void close() throws IOException 
        { 
            if (din == null) 
                return; 
            din.close(); 
        } 
    } 
} 
