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

public class test {

static BufferedReader br;
static long mod = 1000000000 + 7;
static HashSet<Integer> p = new HashSet<>();
static boolean debug =true;
// Arrays.sort(time , (a1,a2) -> (a1[0]-a2[0])); 2d array sort lamda
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pr = new PrintWriter(System.out);
int tc = 1;
tc = cinI();
while (tc-- > 0) {

int n =cinI();
long[] ar=readArray(n,0);

long[] ans= new long[n];

ans[0]=0;

for(int i=1;i<n;i++){
long ansx=0;
for(int j=0;j<31;j++){
long reslast =1<<j;
if((reslast&ar[i-1])==0){
continue;
}
long ax =reslast&ar[i];
if(ax!=0){
continue;
}
ansx|=reslast;

}
ans[i]=ansx;
ar[i]^=ansx;
}
for(int i=0;i<n;i++){
pr.print(ans[i]+" ");
}
pr.println();
}
pr.close();
}

public static <E> void print(String var ,E e){
if(debug==true){
System.out.println(var +" "+e);
}
}
private static long[] sort(long[] e){
ArrayList<Long> x=new ArrayList<>();
for(long c:e){
x.add(c);
}
Collections.sort(x);
long[] y = new long[e.length];
for(int i=0;i<x.size();i++){
y[i]=x.get(i);
}
return y;
}
public static void printDp(long[][] dp) {

int n = dp.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < dp[0].length; j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}
}






private static long gcd(long a, long b) {
if (a == 0)
return b;
if (b == 0)
return a;

// base case
if (a == b)
return a;

// a is greater
if (a > b)
return gcd(a % b, b);
return gcd(a, b % a);
}


public static long min(long a, long b) {
return Math.min(a, b);
}

public static int min(int a, int b) {
return Math.min(a, b);
}


public static void sieve() {
int[] pf = new int[100000000 + 1];
//0 prime //1 not prime
pf[0] = 1;
pf[1] = 1;
for (int j = 2; j <= 10000; j++) {

if (pf[j] == 0) {
p.add(j);
for (int k = j * j; k < pf.length; k += j) {
pf[k] = 1;
}
}
}

}


public static int[] readArray(int n, int x, int z) throws Exception {
int[] arr = new int[n];
String[] ar = cinA();
for (int i = x; i < n + x; i++) {
arr[i] = getI(ar[i - x]);
}
return arr;
}

public static long[] readArray(int n, int x) throws Exception {
long[] arr = new long[n];
String[] ar = cinA();
for (int i = x; i < n + x; i++) {
arr[i] = getL(ar[i - x]);
}
return arr;
}

public static void arrinit(String[] a, long[] b) throws Exception {
for (int i = 0; i < a.length; i++) {
b[i] = Long.parseLong(a[i]);
}
}

public static HashSet<Integer>[] Graph(int n, int edge, int directed) throws Exception {
HashSet<Integer>[] tree = new HashSet[n];

for (int j = 0; j < edge; j++) {

String[] uv = cinA();
int u = getI(uv[0]);
int v = getI(uv[1]);
if (directed == 0) {

tree[v].add(u);
}
tree[u].add(v);
}
return tree;
}

public static void arrinit(String[] a, int[] b) throws Exception {
for (int i = 0; i < a.length; i++) {
b[i] = Integer.parseInt(a[i]);
}
}


static double findRoots(int a, int b, int c) {
// If a is 0, then equation is not
//quadratic, but linear


int d = b * b - 4 * a * c;
double sqrt_val = Math.sqrt(Math.abs(d));


// System.out.println("Roots are real and different \n");

return Math.max((double) (-b + sqrt_val) / (2 * a),
(double) (-b - sqrt_val) / (2 * a));


}

public static String cin() throws Exception {
return br.readLine();
}

public static String[] cinA() throws Exception {
return br.readLine().split(" ");
}

public static String[] cinA(int x) throws Exception {
return br.readLine().split("");
}

public static String ToString(Long x) {
return Long.toBinaryString(x);
}

public static void cout(String s) {
System.out.println(s);
}

public static Integer cinI() throws Exception {
return Integer.parseInt(br.readLine());
}

public static int getI(String s) throws Exception {
return Integer.parseInt(s);
}

public static long getL(String s) throws Exception {
return Long.parseLong(s);
}

public static long max(long a, long b) {
return Math.max(a, b);
}

public static int max(int a, int b) {
return Math.max(a, b);
}

public static void coutI(int x) {
System.out.println(String.valueOf(x));
}

public static void coutI(long x) {
System.out.println(String.valueOf(x));
}

public static Long cinL() throws Exception {
return Long.parseLong(br.readLine());
}

public static void arrInit(String[] arr, int[] arr1) throws Exception {
for (int i = 0; i < arr.length; i++) {
arr1[i] = getI(arr[i]);
}

}
}
