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 JAVA):

Solution:

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Contest {

    final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;
    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new Contest().run();
    }

    void init() throws FileNotFoundException {
        if (ONLINE_JUDGE) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            init();
            solve();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time(ms) = " + (t2 - t1));
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    class MyComparator implements Comparable<MyComparator> {

        int x;
        int y;

        public MyComparator(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(MyComparator a) {
            if (x == a.x) {
                return (y - a.y);
            }
            return x - a.x;
        }
    }

    public static boolean isPrime(int num) {
        if (num > 2 && num % 2 == 0) {
            //System.out.println(num + " is not prime");
            return false;
        }
        int top = (int) Math.sqrt(num) + 1;
        for (int i = 3; i < top; i += 2) {
            if (num % i == 0) {
                //System.out.println(num + " is not prime");
                return false;
            }
        }
        //System.out.println(num + " is prime");
        return true;
    }

    private static long gcd(long a, long b) {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.longValue();
    }

    public void solveE() throws IOException {

    }

    public void solveD() throws IOException {

    }

    public void solve() throws IOException {
        int t = readInt();
        outerloop:
        for (int i = 0; i < t; i++) {
            int n = readInt();
            long[] array = new long[n];
            long sum = 0;
            long xor = readInt();
            sum += xor;
            array[0] = xor;
            for (int j = 1; j < n; j++) {
                array[j] = readInt();
                sum += array[j];
                xor = xor ^ array[j];
            }

            if (2*xor == sum) {
                System.out.println(0);
            } else {
                System.out.println(2);
                long res1 = xor;
                xor ^= res1;
                sum += res1;
                long res2 = sum;
                xor ^= res2;
                sum += res2;
                System.out.println(res1 + " " + res2);
            }
            //System.out.println(sum);
            //System.out.println(xor);
            //System.out.println();
        }
    }

    static int onesComplement(int n) {

        // Find number of bits in the  
        // given integer 
        int number_of_bits
                = (int) (Math.floor(Math.log(n)
                        / Math.log(2))) + 1;

        // XOR the given integer with poe(2, 
        // number_of_bits-1 and print the result 
        return ((1 << number_of_bits) - 1) ^ n;
    }

    public void solveB() throws IOException {
        int t = readInt();
        outerloop:
        for (int i = 0; i < t; i++) {
            int n = readInt();
            int[] array = new int[n];
            for (int j = 0; j < n; j++) {
                array[j] = readInt();
                if (j > 0) {
                    if (Math.abs(array[j] - array[j - 1]) > 1) {
                        System.out.println("YES");
                        //System.out.println(array[j-1] + " " + array[j]);
                        System.out.println(j + " " + (j + 1));
                        continue outerloop;
                    }
                }
            }
            System.out.println("NO");
        }
    }

    public void solveA() throws IOException {
        int t = readInt();
        for (int i = 0; i < t; i++) {
            int n = readInt();
            int k1 = readInt();
            int k2 = readInt();
            boolean first = false;
            int max = 0;
            int[] price1 = new int[k1];
            for (int j = 0; j < k1; j++) {
                price1[j] = readInt();
                if (max < price1[j]) {
                    first = true;
                    max = price1[j];
                }
            }
            int[] price2 = new int[k2];
            for (int j = 0; j < k2; j++) {
                price2[j] = readInt();
                if (max < price2[j]) {
                    first = false;
                    max = price2[j];
                }
            }
            if (first) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }

}