Problem: Given a permutation p of length n, find its subsequence s_1, s_2, …, s_k of length at least 2 such that:

  * |s_1-s_2|+|s_2-s_3|+…+|s_{k-1}-s_k| is as big as possible over all subsequences of p with length at least 2. 
  * Among all such subsequences, choose the one whose length, k, is as small as possible. 



If multiple subsequences satisfy these conditions, you are allowed to find any of them.

A sequence a is a subsequence of an array b if a can be obtained from b by deleting some (possibly, zero or all) elements.

A permutation of length n is an array of length n in which every element from 1 to n occurs exactly once.

Input

The first line contains an integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n (2 ≤ n ≤ 10^5) — the length of the permutation p.

The second line of each test case contains n integers p_1, p_2, …, p_{n} (1 ≤ p_i ≤ n, p_i are distinct) — the elements of the permutation p.

The sum of n across the test cases doesn't exceed 10^5.

Output

For each test case, the first line should contain the length of the found subsequence, k. The second line should contain s_1, s_2, …, s_k — its elements.

If multiple subsequences satisfy these conditions, you are allowed to find any of them.

Example

Input


2
3
3 2 1
4
1 3 4 2


Output


2
3 1 
3
1 4 2 

Note

In the first test case, there are 4 subsequences of length at least 2:

  * [3,2] which gives us |3-2|=1. 
  * [3,1] which gives us |3-1|=2. 
  * [2,1] which gives us |2-1|=1. 
  * [3,2,1] which gives us |3-2|+|2-1|=2. 



So the answer is either [3,1] or [3,2,1]. Since we want the subsequence to be as short as possible, the answer is [3,1].

Solution (in JAVA):

Solution:
import java.util.*;

import java.io.*;
import java.math.BigDecimal;

public class Main {

    public static void main(String[] args) {

        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader inp = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Solver solver = new Solver();
        solver.solve(inp, out);
        out.close();

    }

    static class Solver {

        class pair implements Comparable<pair> {

            int i;
            int cnt;

            public pair(int i, int cnt) {
                this.i = i;
                this.cnt = cnt;
            }

            public int compareTo(pair p) {
                return Long.compare(this.i, p.i);
            }

        }

        class Node implements Comparable<Node> {
            int i;
            int cnt;

            Node(int i, int cnt) {
                this.i = i;
                this.cnt = cnt;
            }

            public int compareTo(Node n) {
                if (this.cnt == n.cnt) {
                    return Integer.compare(this.i, n.i);
                }
                return Integer.compare(this.cnt, n.cnt);
            }
        }

        public boolean done(int[] sp, int[] par) {
            int root;

            root = findSet(sp[0], par);

            for (int i = 1; i < sp.length; i++) {
                if (root != findSet(sp[i], par))
                    return false;
            }
            return true;
        }

        public int findSet(int i, int[] par) {
            int x = i;
            boolean flag = false;
            while (par[i] >= 0) {
                flag = true;
                i = par[i];
            }
            if (flag)
                par[x] = i;
            return i;
        }

        public void unionSet(int i, int j, int[] par) {
            int x = findSet(i, par);
            int y = findSet(j, par);
            if (x < y) {
                par[y] = x;
            } else {
                par[x] = y;
            }
        }

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

            }

        }

        public boolean isPrime(int n) {
            for (int i = 2; i < n; i++) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }

        public void minPrimeFactor(int n, int[] s) {
            boolean prime[] = new boolean[n + 1];
            Arrays.fill(prime, true);
            s[1] = 1;
            s[2] = 2;
            for (int i = 4; i <= n; i += 2) {
                prime[i] = false;
                s[i] = 2;
            }

            for (int i = 3; i <= n; i += 2) {
                if (prime[i]) {
                    s[i] = i;
                    for (int j = 2 * i; j <= n; j += i) {
                        prime[j] = false;
                        s[j] = i;
                    }
                }
            }

        }

        public void findAllPrime(int n, ArrayList<Node> al, int s[]) {
            int curr = s[n];
            int cnt = 1;
            while (n > 1) {
                n /= s[n];
                if (curr == s[n]) {
                    cnt++;
                    continue;

                }
                Node n1 = new Node(curr, cnt);
                al.add(n1);

                curr = s[n];
                cnt = 1;
            }
        }

        public int binarySearch(int n, int k) {
            int left = 1;
            int right = 100000000 + 5;
            int ans = 0;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (n / mid >= k) {
                    left = mid + 1;
                    ans = mid;
                } else {
                    right = mid - 1;
                }
            }

            return ans;
        }

        public boolean checkPallindrom(String s) {
            char ch[] = s.toCharArray();

            for (int i = 0; i < s.length() / 2; i++) {
                if (ch[i] != ch[s.length() - 1 - i])
                    return false;
            }
            return true;
        }

        public boolean pallindrom(String s1, String s2) {
            char ch[] = s1.toCharArray();
            char ch1[] = s2.toCharArray();

            for (int i = 0; i < s1.length(); i++) {
                if (ch[i] != ch1[s1.length() - 1 - i]) {
                    return false;
                }
            }

            return true;
        }

        public void remove(ArrayList<Integer>[] al, int x) {
            for (int i = 0; i < al.length; i++) {
                for (int j = 0; j < al[i].size(); j++) {

                    if (al[i].get(j) == x)
                        al[i].remove(j);

                }
            }
        }

        public long gcd(long a, long b) {
            if (a == 0)
                return b;
            return gcd(b % a, a);
        }

        public void printDivisors(long n, ArrayList<Long> al) {
            // Note that this loop runs till square root
            for (long i = 1; i * i <= (n); i++) {
                if (n % i == 0) {
                    // If divisors are equal, print only one
                    if (n / i == i) {
                        al.add(i);
                    } else // Otherwise print both
                    {
                        al.add(i);
                        al.add(n / i);
                    }

                }
            }
        }

        public static long constructSegment(long seg[], long arr[], int low, int high, int pos) {
            if (low == high) {
                seg[pos] = arr[low];
                return seg[pos];
            }
            int mid = (low + high) / 2;
            long t1 = constructSegment(seg, arr, low, mid, (2 * pos) + 1);
            long t2 = constructSegment(seg, arr, mid + 1, high, (2 * pos) + 2);
            seg[pos] = t1 + t2;
            return seg[pos];

        }

        public static long querySegment(long seg[], int low, int high, int qlow, int qhigh, int pos) {

            if (qlow <= low && qhigh >= high) {
                return seg[pos];
            } else if (qlow > high || qhigh < low) {
                return 0;
            } else {
                long ans = 0;
                int mid = (low + high) / 2;
                ans += querySegment(seg, low, mid, qlow, qhigh, (2 * pos) + 1);
                ans += querySegment(seg, mid + 1, high, qlow, qhigh, (2 * pos) + 2);
                return ans;
            }

        }

        public static int lcs(char[] X, char[] Y, int m, int n) {
            if (m == 0 || n == 0)
                return 0;
            if (X[m - 1] == Y[n - 1])
                return 1 + lcs(X, Y, m - 1, n - 1);
            else
                return Integer.max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
        }

        public static long recursion(long start, long end, long cnt[], int a, int b) {

            long min = 0;
            long count = 0;
            int ans1 = -1;
            int ans2 = -1;
            int l = 0;
            int r = cnt.length - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (cnt[mid] >= start) {
                    ans1 = mid;
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }

            l = 0;
            r = cnt.length - 1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (cnt[mid] <= end) {
                    ans2 = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }

            if (ans1 == -1 || ans2 == -1 || ans2 < ans1) {
                // System.out.println("min1 "+min);
                min = a;
                return a;

            } else {
                min = b * (end - start + 1) * (ans2 - ans1 + 1);
            }
            if (start == end) {
                // System.out.println("min "+min);
                return min;
            }
            long mid = (end + start) / 2;
            min = Long.min(min, recursion(start, mid, cnt, a, b) + recursion(mid + 1, end, cnt, a, b));
            // System.out.println("min "+min);
            return min;
        }

        public int lowerBound(ArrayList<Long> al, long ele) {
            int l = 0;
            int r = al.size() - 1;
            int ans = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (al.get(mid) <= ele) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }

            }
            return ans;
        }

        public int lowerBound(long arr[], long ele) {
            int l = 0;
            int r = arr.length - 1;
            int ans = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (arr[mid] <= ele) {
                    ans = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }

            }
            return ans;
        }

        public long dfs_util(ArrayList<Integer>[] al, boolean vis[], int x, long arr[], long val) {

            vis[x] = true;

            long temp = 0;
            for (int i = 0; i < al[x].size(); i++) {

                if (!vis[al[x].get(i)]) {

                    temp += dfs_util(al, vis, al[x].get(i), arr, val + 1);
                }

            }
            arr[x] = val - (temp);
            return (temp + 1);

        }

        public long[] dfs(ArrayList[] al) {
            long arr[] = new long[al.length];
            boolean vis[] = new boolean[al.length];
            for (int i = 0; i < al.length; i++) {
                if (!vis[i]) {
                    dfs_util(al, vis, i, arr, 0);
                }
            }
            return arr;

        }

        public void permute(String s, int l, int r, ArrayList<String> al) {
            if (l == r) {
                al.add(s);

            }
            for (int i = l; i <= r; i++) {
                String str = swap(s, l, i);
                permute(str, l + 1, r, al);

            }

        }

        public String swap(String s, int l, int r) {
            char ch[] = s.toCharArray();
            char tem = ch[l];
            ch[l] = ch[r];
            ch[r] = tem;
            return String.valueOf(ch);
        }

        public int[] computeLps(String s) {
            int ans[] = new int[s.length()];
            char ch[] = s.toCharArray();
            int n = s.length();
            int i = 1;
            int len = 0;
            ans[0] = 0;
            while (i < n) {
                if (ch[i] == ch[len]) {
                    len++;
                    ans[i] = len;
                    i++;
                } else {
                    if (len != 0) {
                        len = ans[len - 1];
                    } else {
                        ans[i] = len;
                        i++;
                    }
                }
            }

            return ans;

        }

        public int longestPrefixSuffix(String s) {
            int n = s.length();

            if (n < 2) {
                return 0;
            }

            int len = 0;
            int i = n / 2;
            while (i < n) {
                if (s.charAt(i) == s.charAt(len)) {
                    ++len;
                    ++i;
                } else {
                    if (len == 0) {
                        ++i;
                    } else {

                        --len;
                    }
                }
            }

            return len;

        }

        public boolean convertFromBaseToBase(long num, int fromBase, int toBase, HashSet<Integer> hs) {
            StringBuilder s = new StringBuilder();
            boolean f = true;
            int cnt = 0;
            while (num > 0) {
                long tem = num % toBase;
                if (tem == 1) {
                    if (hs.contains(cnt)) {
                        f = false;
                        break;
                    } else {
                        hs.add(cnt);
                    }
                } else if (tem == 0) {

                } else {
                    f = false;
                    break;
                }
                num /= toBase;
                cnt++;

            }

            return f;

        }

        private boolean possible(long arr[], long d, long k) {
            long tem = 0;
            for (int i = 0; i < arr.length - 1; i++) {
                tem += (arr[i + 1] - arr[i]) / (d);

                if ((arr[i + 1] - arr[i]) % d == 0)
                    tem--;

            }
            if (tem <= k) {
                return true;
            } else
                return false;

        }

        public void bfsUtil(ArrayList<Integer> a[], int out[]) {
            boolean vis[] = new boolean[a.length];
            for (int i = 0; i < a.length; i++) {
                if (!vis[i]) {
                    bipartie(a, vis, out, i);
                }
            }
        }

        public int[] bipartie(ArrayList<Integer> arr[], boolean vis[], int color[], int e) {

            Queue<Integer> q = new LinkedList<>();
            color[e] = 1;
            q.add(e);
            while (!q.isEmpty()) {
                int x = q.remove();
                if (vis[x]) {
                    continue;
                }
                vis[x] = true;
                for (int i = 0; i < arr[x].size(); i++) {
                    if (!vis[arr[x].get(i)]) {

                    } else {
                        if (color[arr[x].get(i)] == color[x]) {
                            color[x] = 2;
                        }
                    }
                }

                for (int i = 0; i < arr[x].size(); i++) {
                    if (!vis[arr[x].get(i)]) {
                        if (color[x] == 2) {
                            color[arr[x].get(i)] = 0;

                        } else {
                            color[arr[x].get(i)] = 1 - color[x];

                        }
                        q.add(arr[x].get(i));
                    }

                }
            }
            return color;
        }

        public int dfs1(ArrayList<Integer> al[], int x, boolean arr[], int val, boolean vis[], long ans[]) {
            vis[x] = true;
            if (arr[x]) {

                ans[0] += (long) val;
            }
            for (int i = 0; i < al[x].size(); i++) {

                if (!vis[al[x].get(i)]) {
                    int temp = val;
                    if (!arr[x])
                        temp++;
                    dfs1(al, al[x].get(i), arr, temp, vis, ans);
                }

            }
            return 0;
        }

        private void solve(InputReader inp, PrintWriter out1) {

            int t = inp.nextInt();
            for (int k = 0; k < t; k++) {
                int n = inp.nextInt();
                long arr[] = new long[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = inp.nextLong();
                }
                Stack<Long> s = new Stack<Long>();
                s.push(arr[0]);
                s.push(arr[1]);

                for (int i = 2; i < n; i++) {
                    long x = s.pop();
                    long y = s.pop();
                    long tem1 = Math.abs(x - arr[i]) + Math.abs(x - y);
                    long tem2 = Math.abs(y - arr[i]);
                    if (tem2 >= tem1) {
                        s.push(y);
                        s.add(arr[i]);
                    } else {
                        s.push(y);
                        s.push(x);
                        s.push(arr[i]);
                    }
                }

                long ans[] = new long[s.size()];
                int p = 0;
                while (!s.isEmpty()) {
                    ans[p] = s.pop();
                    p++;
                }
                out1.println(ans.length);
                for (int i = ans.length - 1; i >= 0; i--) {
                    out1.print(ans[i] + " ");
                }
                out1.println();
            }

        }

    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}

class ele implements Comparable<ele> {
    int i;
    int val;

    public ele(int i, int val) {
        this.i = i;
        this.val = val;

    }

    @Override
    public int compareTo(ele e) {

        if ((e.val - e.i) == (this.val - this.i)) {
            return Integer.compare(this.i, e.i);
        }
        return Integer.compare(e.val - e.i, this.val - this.i);

    }
}