Problem: Let's call an array a_1, a_2, ..., a_m of nonnegative integer numbers good if a_1 + a_2 + ... + a_m = 2⋅(a_1 ⊕ a_2 ⊕ ... ⊕ a_m), where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

For example, array [1, 2, 3, 6] is good, as 1 + 2 + 3 + 6 = 12 = 2⋅ 6 = 2⋅ (1⊕ 2 ⊕ 3 ⊕ 6). At the same time, array [1, 2, 1, 3] isn't good, as 1 + 2 + 1 + 3 = 7 ≠ 2⋅ 1 = 2⋅(1⊕ 2 ⊕ 1 ⊕ 3).

You are given an array of length n: a_1, a_2, ..., a_n. Append at most 3 elements to it to make it good. Appended elements don't have to be different. It can be shown that the solution always exists under the given constraints. If there are different solutions, you are allowed to output any of them. Note that you don't have to minimize the number of added elements!. So, if an array is good already you are allowed to not append elements.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10 000). The description of the test cases follows.

The first line of each test case contains a single integer n (1≤ n ≤ 10^5) — the size of the array.

The second line of each test case contains n integers a_1, a_2, ..., a_n (0≤ a_i ≤ 10^9) — the elements of the array.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Output

For each test case, output two lines.

In the first line, output a single integer s (0≤ s≤ 3) — the number of elements you want to append.

In the second line, output s integers b_1, ..., b_s (0≤ b_i ≤ 10^{18}) — the elements you want to append to the array.

If there are different solutions, you are allowed to output any of them.

Example

Input


3
4
1 2 3 6
1
8
2
1 1


Output


0

2
4 4
3
2 6 2

Note

In the first test case of the example, the sum of all numbers is 12, and their ⊕ is 6, so the condition is already satisfied.

In the second test case of the example, after adding 4, 4, the array becomes [8, 4, 4]. The sum of numbers in it is 16, ⊕ of numbers in it is 8.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long POW(long long x, long long n) {
  x %= MOD;
  if (n == 0) return 1;
  if (n % 2 == 0) return POW(x * x, n / 2) % MOD;
  return x % MOD * POW(x, n - 1) % MOD;
}
long long POW2(long long x, long long n) {
  if (n == 0) return 1;
  if (n % 2 == 0) return POW2(x * x, n / 2);
  return x * POW2(x, n - 1);
}
long long POW3(long long x, long long n, long long m) {
  x %= m;
  if (n == 0) return 1;
  if (n % 2 == 0) return POW3(x * x, n / 2, m) % m;
  return x * POW3(x, n - 1, m) % m;
}
long long gcd(long long u, long long v) {
  long long r;
  while (0 != v) {
    r = u % v;
    u = v;
    v = r;
  }
  return u;
}
long long lcm(long long u, long long v) { return u / gcd(u, v) * v; }
long long KAI(long long m) {
  if (m < 0) return 0;
  if (m == 0) return 1;
  return m * KAI(m - 1) % MOD;
}
long long KAI2(long long m) {
  if (m < 0) return 0;
  if (m == 0) return 1;
  return m * KAI2(m - 1);
}
long long extGCD(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extGCD(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
inline long long mod(long long a, long long m) { return (a % m + m) % m; }
long long modinv(long long a) {
  long long x, y;
  extGCD(a, MOD, x, y);
  return mod(x, MOD);
}
long long COM(long long m, long long n) {
  if (m < n) return 0;
  if (n < 0) return 0;
  if (n == 0) return 1;
  if (m == n) return 1;
  return KAI(m) % MOD * modinv(KAI(n) % MOD * KAI(m - n) % MOD) % MOD;
}
long long COM2(long long m, long long n) {
  if (m < n) return 0;
  if (n < 0) return 0;
  if (n == 0) return 1;
  if (m == n) return 1;
  return KAI2(m) / KAI2(n) / KAI2(m - n);
}
long long DEC(long long x, long long m, long long n) {
  return x % POW2(m, n + 1) / POW2(m, n);
}
long long keta(long long x, long long n) {
  if (x == 0) return 0;
  return keta(x / n, n) + 1;
}
long long DIV(long long x, long long n) {
  if (x == 0) return 0;
  return x / n + DIV(x / n, n);
}
long long ORD(long long x, long long n) {
  if (x == 0) return (1e18);
  if (x % n != 0) return 0;
  return 1 + ORD(x / n, n);
}
long long SUP(long long x, long long n) {
  if (x == 0) return 0;
  if (x % n != 0) return x;
  return SUP(x / n, n);
}
long long DigSum(long long n) {
  if (n == 0) return 0;
  return n % 10 + DigSum(n / 10);
}
long long SGS(long long x, long long y, long long m) {
  if (y == 0) return 0;
  if (y % 2 == 0) {
    return (1 + POW3(x, y / 2, m)) * SGS(x, y / 2, m) % m;
  }
  return (1 + x * SGS(x, y - 1, m)) % m;
}
long long SSGS(long long x, long long y, long long m) {
  if (y == 0) return 0;
  if (y == 1) return 1;
  if (y % 2 == 0) {
    return (SSGS(x, y / 2, m) * (POW3(x, y / 2, m) + 1) % m +
            SGS(x, y / 2, m) * y / 2 % m) %
           m;
  }
  return (SSGS(x, y - 1, m) * x % m + y) % m;
}
void shuffle(long long array[], long long size) {
  for (long long i = 0; i < size; i++) {
    long long j = rand() % size;
    long long t = array[i];
    array[i] = array[j];
    array[j] = t;
  }
}
long long SQRT(long long n) {
  long long ok, ng, mid;
  ng = n + 1;
  if (303700500 < ng) ng = 303700500;
  ok = 0;
  while (abs(ok - ng) > 1) {
    mid = (ok + ng) / 2;
    if (mid * mid <= n) {
      ok = mid;
    } else {
      ng = mid;
    }
  }
  return ok;
}
struct UnionFind {
  vector<int> par;
  vector<int> sizes;
  UnionFind(int n) : par(n), sizes(n, 1) {
    for (long long i = 0; i < n; i++) par[i] = i;
  }
  int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (sizes[x] < sizes[y]) swap(x, y);
    par[y] = x;
    sizes[x] += sizes[y];
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return sizes[find(x)]; }
};
map<int64_t, int> prime_factor(int64_t n) {
  map<int64_t, int> ret;
  for (int64_t i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}
bool is_prime(int64_t x) {
  if (x == 1) return false;
  for (int64_t i = 2; i * i <= x; i++) {
    if (x % i == 0) return false;
  }
  return true;
}
struct edge {
  long long to, cost;
};
struct graph {
  long long V;
  vector<vector<edge> > G;
  vector<long long> d;
  graph(long long n) { init(n); }
  void init(long long n) {
    V = n;
    G.resize(V);
    d.resize(V);
    for (long long i = 0; i < V; i++) {
      d[i] = (1e18);
    }
  }
  void add_edge(long long s, long long t, long long cost) {
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }
  void dijkstra(long long s) {
    for (long long i = 0; i < V; i++) {
      d[i] = (1e18);
    }
    d[s] = 0;
    priority_queue<pair<long long, long long>,
                   vector<pair<long long, long long> >,
                   greater<pair<long long, long long> > >
        que;
    que.push(pair<long long, long long>(0, s));
    while (!que.empty()) {
      pair<long long, long long> p = que.top();
      que.pop();
      long long v = p.second;
      if (d[v] < p.first) continue;
      for (auto e : G[v]) {
        if (d[e.to] > d[v] + e.cost) {
          d[e.to] = d[v] + e.cost;
          que.push(pair<long long, long long>(d[e.to], e.to));
        }
      }
    }
  }
};
long long d[3100][3100];
void warshall_floyd(long long n) {
  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < n; j++)
      for (long long k = 0; k < n; k++)
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}
struct bit {
  long long m;
  vector<long long> b;
  bit(long long i) {
    m = i;
    b.resize(m + 1);
  }
  long long num(long long i) { return b[i]; }
  long long sum(long long i) {
    long long s = 0;
    while (i > 0) {
      s += b[i];
      i -= i & -i;
    }
    return s;
  }
  void add(long long i, long long x) {
    while (i <= m) {
      b[i] += x;
      i += i & -i;
    }
  }
};
int main() {
  long long t, n, a[110000], x, y;
  cin >> t;
  for (long long i = 0; i < t; i++) {
    cin >> n;
    for (long long j = 0; j < n; j++) cin >> a[j];
    x = 0;
    y = 0;
    for (long long j = 0; j < n; j++) {
      x += a[j];
      y ^= a[j];
    }
    printf("2\n");
    printf("%lld %lld\n", x + y, y);
  }
}