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.*;

public class cf {
	static Reader sc = new Reader();
	static PrintWriter out = new PrintWriter(System.out);

	static long mod = (long) 1e9 + 7;

	// 1..9 11..99 111.999 1111.9999

	public static void main(String[] args) {
		int tc = sc.ni();
		while (tc-- > 0) {
			int n = sc.ni();
			int[] arr = sc.nai(n);
			int[] b = new int[n];
			int prev = arr[0];
			for (int i = 1; i < n; i++) {
				boolean[] temp = new boolean[32];
				int req = 0;
				for (int k = 0; k < 32; k++) {
					if ((prev & (1 << k)) > 0)
						temp[k] = true;
				}
				for (int k = 0; k < 32; k++) {
					if ((arr[i] & (1 << k)) == 0) {
						if (temp[k])
							req |= (1 << k);
					}
				}
				b[i] = req;
				prev = b[i] ^ arr[i];
			}
			for (int e : b)
				out.print(e + " ");
			out.println();
		}
		out.close();
	}

	public static long pow(long a, long b, long m) {
		if (b == 0) {
			return 1;
		}
		if (b % 2 == 0) {
			return pow((a * a) % m, b / 2, m) % m;
		} else {
			return (a * pow((a * a) % m, b / 2, m)) % m;
		}
	}

	// snippets

	static class Pair implements Comparable<Pair> {
		int x;
		int y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;

		}

		@Override
		public int compareTo(Pair o) {
			if (this.x > o.x)
				return 1;
			else if (this.x < o.x)
				return -1;
			else {
				if (this.y > o.y)
					return 1;
				else if (this.y < o.y)
					return -1;
				else
					return 0;
			}
		}

		public int hashCode() {
			int ans = 1;
			ans = x * 31 + y * 13;
			return ans;
		}

		@Override
		public boolean equals(Object o) {
			if (this == o) {
				return true;
			}
			if (o == null) {
				return false;
			}
			if (this.getClass() != o.getClass()) {
				return false;
			}
			Pair other = (Pair) o;
			if (this.x == other.x && this.y == other.y) {
				return true;
			}
			return false;
		}

	}

	static void add_map(HashMap<Integer, Integer> map, int v) {
		if (!map.containsKey(v)) {
			map.put(v, 1);
		} else {
			map.put(v, map.get(v) + 1);
		}
	}

	static void remove_map(HashMap<Integer, Integer> map, int v) {
		if (map.containsKey(v)) {
			map.put(v, map.get(v) - 1);
			if (map.get(v) == 0)
				map.remove(v);
		}
	}

	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 void sort(int[] arr) {
		// shuffle
		Random rand = new Random();
		for (int i = 0; i < arr.length; i++) {
			int j = rand.nextInt(i + 1);
			int tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
		Arrays.sort(arr);
	}

	static void sort(long[] arr) {
		// shuffle
		Random rand = new Random();
		for (int i = 0; i < arr.length; i++) {
			int j = rand.nextInt(i + 1);
			long tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
		Arrays.sort(arr);
	}

	static boolean isPrime(int n) {
		if (n <= 1)
			return false;
		if (n <= 3)
			return true;
		if (n % 2 == 0 || n % 3 == 0)
			return false;
		double sq = Math.sqrt(n);

		for (int i = 5; i <= sq; i = i + 6)
			if (n % i == 0 || n % (i + 2) == 0)
				return false;
		return true;
	}

	static boolean isPrime(long n) {
		if (n <= 1)
			return false;
		if (n <= 3)
			return true;
		if (n % 2 == 0 || n % 3 == 0)
			return false;
		double sq = Math.sqrt(n);

		for (int i = 5; i <= sq; i = i + 6)
			if (n % i == 0 || n % (i + 2) == 0)
				return false;
		return true;
	}

	static void print_arr(int A[]) {
		for (int i : A) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	static void print_arr(long A[]) {
		for (long i : A) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	static void print_arr(char A[]) {
		for (char i : A) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

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

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

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

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

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

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

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

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

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

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

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

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

	static int max(int A[]) {
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < A.length; i++) {
			max = Math.max(max, A[i]);
		}
		return max;
	}

	static int min(int A[]) {
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < A.length; i++) {
			min = Math.min(min, A[i]);
		}
		return min;
	}

	static long max(long A[]) {
		long max = Long.MIN_VALUE;
		for (int i = 0; i < A.length; i++) {
			max = Math.max(max, A[i]);
		}
		return max;
	}

	static long min(long A[]) {
		long min = Long.MAX_VALUE;
		for (int i = 0; i < A.length; i++) {
			min = Math.min(min, A[i]);
		}
		return min;
	}

	static long sum(int A[]) {
		long sum = 0;
		for (int i : A) {
			sum += i;
		}
		return sum;
	}

	static long sum(long A[]) {
		long sum = 0;
		for (long i : A) {
			sum += i;
		}
		return sum;
	}

	static ArrayList<Integer> sieve(int n) {
		ArrayList<Integer> primes = new ArrayList<>();
		boolean[] isPrime = new boolean[n];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;
		for (int i = 2; i * i <= n; i++) {
			if (isPrime[i]) {
				for (int j = i * i; j < n; j += i) {
					isPrime[j] = false;
				}
			}
		}
		for (int i = 2; i < n; i++) {
			if (isPrime[i])
				primes.add(i);
		}
		return primes;
	}

	static class Reader {
		BufferedReader br;
		StringTokenizer st;

		Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer("");
		}

		Reader(File f) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(f));
			st = new StringTokenizer("");
		}

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

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

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

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

		int[] nai(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = ni();
			return a;
		}

		long[] nal(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nl();
			return a;
		}
	}

}