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.io.*;
import java.util.*;
import java.math.*;
import java.text.DecimalFormat;
import java.text.NumberFormat;
 

@SuppressWarnings("unchecked")
public class Main {
      
    int mod = 1000000007;

    public class SegmentTree{

       int n;
       long[] tree;

       SegmentTree(long[] arr){

          this.n = arr.length; 
          this.tree = new long[2 * n];

          for(int i = n; i < 2 * n; i++){
              this.tree[i] = arr[i - n];
          }

          for(int i = n - 1; i >= 1; i--){
              this.tree[i] = this.tree[2 * i] + this.tree[2 * i + 1];
          }

       }

       public long query(int l, int r){

          long res = 0;
          l = l + n;
          r = r + n;

          while(l < r){

              if(l % 2 == 1){
                  res = res + tree[l]; 
                  l++;
              }

              if(r % 2 == 1){
                  r--;
                  res = res + tree[r];
              }

              l /= 2;
              r /= 2;
          }

          return res;
       }

       public void update(int idx, long v){
          
          idx += n; this.tree[idx] += v;
          while(idx > 1){
             idx /= 2;
             this.tree[idx] = this.tree[2 * idx] + this.tree[2 * idx + 1];
          }
       }


    }


    public class DSU{

       int[] parent;
       int[] size;

       DSU(int n){
          
          this.parent = new int[n + 1];
          for(int i = 1; i <= n; i++) parent[i] = i;
          this.size = new int[n + 1];
       
       }

       public int find(int root){
          
          if(root == parent[root]) return root;
          int p = find(parent[root]);
          parent[root] = p;
          return p;

       }

       public void union(int u, int v){

          int pu = find(u);
          int pv = find(v);
          if(pu == pv) return;
          parent[pv] = pu;
          size[pu] = Math.max(Math.max(size[pu], size[pv]), (size[pu] + 1) / 2 + (size[pv] + 1) / 2 + 1);
       }

       public void merge(int u, int v){

          int pu = find(u);
          int pv = find(v);
          parent[pv] = pu;
          size[pu] += size[pv];
       
       }

    }

    public int longest(int[] aa, int a){

       int n = aa.length; 
       int longest = -1;
       int sum = 0;
       for(int i = 0; i < n; i++){
          sum += aa[i];
          if(sum % a != 0){
             longest = Math.max(longest, i + 1);
          }
       }

       sum = 0;
       for(int i = n - 1; i >= 0; i--){
          sum+= aa[i];
          if(sum % a != 0){
             longest = Math.max(longest, n - i);
          }
       }
         
       return longest;

    }


    public void solve() throws IOException{
    
       int t = in.nextInt();

       for(int i = 0; i < t; i++){

           int n = in.nextInt();
           Stack<Integer> s = new Stack<>();
           int inc = 0;
           for(int j = 0; j < n; j++){
               int num = in.nextInt(); 
               if(s.isEmpty()){
                  s.add(num);
               }else if(num > s.peek()){

                  if(inc == 1){
                     s.pop();
                     s.add(num);
                  }else if(inc == -1){
                     s.add(num);
                     inc = 1;
                  }else if(inc == 0){
                     inc = 1;
                     s.add(num);
                  }

               }else if(num < s.peek()){
                  
                  if(inc == 1){
                     s.add(num);
                     inc = -1;
                  }else if(inc == -1){
                     s.pop();
                     s.add(num);
                  }else if(inc == 0){
                     inc = -1;
                     s.add(num);
                  }

               }
           }

           List<Integer> res = new ArrayList<>();
           while(!s.isEmpty()){
               res.add(s.pop());
           }

           out.println(res.size());
           for(int k = res.size() - 1; k >= 0; k--){
              out.print(res.get(k) + " ");
           }
           out.println();

       }

    }


    FastScanner in;
    PrintWriter out;
    
    static class FastScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(InputStream in) {
            br = new BufferedReader(new InputStreamReader(in));
            st = null;
        }
 
        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
 
        String nextLine() throws IOException {
            if (st == null || !st.hasMoreTokens())
                return br.readLine();
            StringBuilder result = new StringBuilder(st.nextToken());
            while (st.hasMoreTokens()) {
                result.append(" ");
                result.append(st.nextToken());
            }
            return result.toString();
        }
 
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        long nextLong() throws IOException {
            return Long.parseLong(next());
        }
 
        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
    }
 
    void run() throws IOException {
        in = new FastScanner(System.in);
        out = new PrintWriter(System.out, false);
        solve();
        out.close();
    }
 
    public static void main(String[] args) throws IOException{
        new Main().run();
    }
 
    public void printArr(int[] arr){
        for(int i = 0; i < arr.length; i++){
            out.print(arr[i] + " ");
        }
        out.println();
    }
 
    public long gcd(long a, long b){
        if(a == 0) return b;
        return gcd(b % a, a);
    }

    public boolean isPrime(long num){

        if(num == 0 || num == 1){
            return false;
        }

        for(int i = 2; i * i <= num; i++){
            if(num % i == 0){
                return false;
            }
        }

        return true;
    }

    public class Pair<A, B>{
        public A x; 
        public B y;

        Pair(A x, B y){
            this.x = x;
            this.y = y;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            if (!x.equals(pair.x)) return false;
            return y.equals(pair.y);
        }

        @Override
        public int hashCode() {
            int result = x.hashCode();
            result = 31 * result + y.hashCode();
            return result;
        }

    }

    class Tuple{
        int x; int y; int z;
        Tuple(int ix, int iy, int iz){
            x = ix;
            y = iy;
            z = iz;
        }
    }
}