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.*;
 
 
public class gfg  {

    
    public static void main(String[] args) throws IOException{
        //Reader.init(System.in);
        //PrintWriter out = new PrintWriter(System.out);
        Reader.init(System.in);
        int t = Reader.nextInt();
        while(t-->0){
           solve();
        }
            //out.close();
    }
    
    static TreeSet<Integer>[] graph;
    //static ArrayList<Integer>[] set;
    static int n=0;
    static int m=0;
    static boolean[] vis;
    //static char[][] arr;
    static long mod =1000000007;
    static int min=-1;
    //static ArrayList<int[]> list ;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    static void solve()throws IOException{
        n = Reader.nextInt();
        int[] arr = new int[n];

        for(int i=0;i<n;i++){
            int a = Reader.nextInt();
            arr[i] = a;
        }
        int prev = arr[0];
        ArrayList<Integer> list = new ArrayList<>();
        list.add(prev);
        // boolean inc = false;
        // boolean dec = false;
        boolean empty = true;
        long sum=0;
        int prevadded = 0;
        //int prev=arr[0];
        for(int i=1;i<n;i++){
            int a = arr[i-1];
            int b = arr[i];
            int c=0;
            if(i<n-1)
                c= arr[i+1];
            // for max
            if(b>a ){
                if(i<n-1 && c>b){
                    continue;
                }
                else
                    list.add(b);
                // empty = false;
                // sum+=(Math.abs(prev-b));
                // prevadded = Math.abs(prev-b);
                // prev = b;
                //System.out.println("max "+a+" "+b+" "+c);
            }
            // for min;
            else {  
                if(i<n-1 && c<b)
                    continue;
                else
                    list.add(b);
                // empty =false;
                // sum+=(Math.abs(prev-b));
                // prevadded= Math.abs(prev-b);
                // prev = b;
                //System.out.println(a+" "+b+" "+c);
            }

        }
        
        System.out.println(list.size());
        for(int i=0;i<list.size();i++)
            System.out.print(list.get(i)+" ");
        System.out.println();


    }

    

    


    
    
    // ggratest common divisor
    static int gcd(int a , int b){
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
 
    // least common multiple
    static int lcm(int a, int b){
        return (a*b)/gcd(a,b);
    }
    
    // a^b
    static long fastpow(long a, long b){
        long res = 1;a=a%mod;
        while(b>0){
            if(b%2==1)
                res = (res*a)%mod;
            a = (a*a)%mod;
            b = b>>1;
        }
        return res;
    }
 
    
}
 
 
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
 
    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
 
    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }
 
    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
    
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}
class newcomparator implements Comparator<Integer>{
    //@Override
    public int compare(Integer a, Integer  b){
        return a<=b?1:-1;
    }
 }
class node {
    int a;
    long b;// cost to rreach\
    node(int s,long va){
        a=s;
        b=va;
    }
}
class mergesort{
    static void sort(int l, int h, int[] arr){
        if(l<h){
            int mid = (l+h)/2;
            
            sort(l,mid,arr);
            sort(mid+1,h,arr);
            merge(l,mid,h,arr);
        }
    }
    static void merge(int l, int m , int h , int [] arr){
 
        int[] left = new int[m-l+1];
        int[] right = new int[h-m];
        for(int i= 0 ;i< m-l+1;i++){
            left[i] = arr[l+i];
        }
        for(int i=0;i<h-m;i++){
            right[i] = arr[m+1+i];
        }
        //now left and right arrays are assumed to be sorted and we have tp merge them together 
        // int the original aaray.
        int i=l;
        int lindex = 0;
        int rindex =  0;
        
        while(lindex<m-l+1 && rindex<h-m){
            if(left[lindex]<=right[rindex]){
                arr[i]=left[lindex];
                lindex++;
                i++;
            }
            else{
                arr[i]=right[rindex];
                rindex++;
                i++;
            }
        }
        while(lindex<m-l+1){
            arr[i]=left[lindex];
            lindex++;
            i++;
        }
        while(rindex<h-m){
            arr[i]=right[rindex];
            rindex++;
            i++;
        }
    }
    
}