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 
#include<iostream>
#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
using namespace std;
#define ll long long
#define INF 1000007
#define MAX 1005
#define EPS 1e-9
// #define PI acos(-1.0)
#define nl "\n"
#define F first
#define S second
typedef vector<ll> vi;
typedef priority_queue<ll , vector<ll> , greater<ll> > pqmx;
typedef priority_queue<ll> pqmn;
typedef pair<ll , ll> pi;
typedef pair<ll , ll> ii;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector< pair<ll , ll> > vpi;
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define yeS(GOOD)      GOOD ? cout<<"YES\n" : cout<<"NO\n"
#define all(a) a.begin() , a.end()
#define pb push_back
#define ar array

constexpr int mod = (int)1e9 + 7;

ll binpow(ll a, ll b,ll mod){ll res=1;a%=mod;while(b>0){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
ll binmul(ll a, ll b){ll res=0;a%=mod;while(b>0){if(b&1)res=(res + a)%mod;a=(a + a)%mod;b>>=1;}return res;}
ll area(pi a, pi b,pi c){return abs(a.F * b.S + b.F * c.S + c.F*a.S - a.S * b.F - b.S * c.F - c.S * a.F);}
ll gcd (ll a,ll b){if(b==0)return a;else return gcd (b, a % b);}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
ll min(ll a,ll b){if(a < b){return a;}return b;}
ll max(ll a,ll b){if(a > b){return a;}return b;}
double intlog(ll n ,ll base){return (double)log(n)/log(base);}

template <int mod>
struct modint {
    int value;
    modint(long long x= 0) { value = normalize(x); }
    int normalize(long long x) {if (x < -mod || x >= mod)x %= mod;
    if (x < 0)x += mod;return static_cast<int>(x);}
    explicit operator int() const { return value; }
    modint operator-() const { return modint(-value); }
    modint &operator+=(modint rhs) {if ((value += rhs.value) >= mod)value -= mod;return *this;}
    modint &operator-=(modint rhs) {if ((value -= rhs.value) < 0)value += mod;return *this;}
    modint &operator*=(modint rhs) {value = normalize(static_cast<long long>(value) * rhs.value);return *this;}
    modint &operator/=(modint rhs) { return *this *= modint(inverse(rhs.value, mod)); }
    int inverse(int a, int m) {int u = 0, v = 1;while (a != 0) {int t = m / a;m -= t * a;swap(a, m);u -= t * v;swap(u, v);}
        assert(m == 1);return u;}
    bool operator==(modint rhs) const { return value == rhs.value; }
    bool operator!=(modint rhs) const { return !(*this == rhs); }
    friend modint operator+(modint lhs, modint rhs) { return lhs += rhs; }
    friend modint operator-(modint lhs, modint rhs) { return lhs -= rhs; }
    friend modint operator*(modint lhs, modint rhs) { return lhs *= rhs; }
    friend modint operator/(modint lhs, modint rhs) { return lhs /= rhs; }
};

using mint = modint<mod>;


ll t , m , temp , temp2, root ,q , k , i , j , r , u , v , w,n,p;

struct Node{
    int pos;
    int val;
};

int main(){
#ifndef ONLINE_JUDGE
    freopen("input.txt" , "r" ,stdin);
    freopen("output.txt" , "w" , stdout);
#endif
    cin>>t;
    while(t--){
        cin>>n;
        vi a(n);
        fr(i , n){
            cin>>a[i];
        }
        int last = 0;
        cout<<0<<" ";
        p = a[0];
        rep(i , 1 , n){
            if((a[i] & a[i - 1]) == a[i - 1]){
                cout<<0<<" ";
            }
            else{
                int p = 0;
                for(int j = 0;j < 30;j++){
                    if((a[i-1] & (1 << j)) && !(a[i] & (1 << j))){
                        p = p | (1 << j);
                    }
                }
                cout<<p<<" ";
                a[i] = a[i] ^ p;
            }
        }
        cout<<nl;
    }
#ifndef ONLINE_JUDGE
    cout << "Running Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s .\n";
#endif
}