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.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;
import java.math.*;
import java.io.*;
import java.text.*;
import java.math.BigInteger;

public class Main
{  

    //Life's a bitch
    public static boolean[] sieve(long n)
    {
        boolean[] prime = new boolean[(int)n+1];
        Arrays.fill(prime,true);
        prime[0] = false;
        prime[1] = false;
        long m = (long)Math.sqrt(n);
        for(int i=2;i<=m;i++)
        {
            if(prime[i])
            {
                for(int k=i*i;k<=n;k+=i)
                {
                    prime[k] = false;
                }
            }
        }
        return prime;
    } 

    
    static long GCD(long a,long b)
    {
        if(b==0)
        {
            return a;
        }
        return GCD(b,a%b);
    }

    static long CountCoPrimes(long n)
    {
        long res = n;
        for(int i=2;i*i<=n;i++)
        {
            if(n%i==0)
            {
                while(n%i==0)
                {
                    n/=i;
                }
                res-=res/i;
            }
        }
        if(n>1)
        {
            res-=res/n;
        }
        return res;
    }


    

    

    static boolean prime(int n)
    {
        for(int i=2;i*i<=n;i++)
        {
            if(i%2==0 ||i%3==0)
            {
                return false;
            }
        }
        return true;
    }

   


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


   

    static void reverse(char[] a)
    {
        // char[] a = c.toCharArray();
        int start=0;
        int end = a.length-1;
        while(start!=end)
        {
            char temp = a[start];
            a[start] = a[end];
            a[end] = temp;
            start++;
            end--;
        }
    }

   


    
   
    Scanner in = new Scanner(System.in);
    void run() throws IOException
    {
        
        
       int t = ni();
       while(t-->0)
       {
            int n = ni();
            int[] a = new int[n];
            for(int i=0;i<n;i++){
                a[i] = ni();
            }

            ArrayList<Integer> ans = new ArrayList<>();
            ans.add(a[0]);
            for(int i=1;i<n-1;i++){
                if( a[i]<a[i-1] && a[i]<a[i+1] || (a[i]>a[i-1] && a[i]>a[i+1])){
                    ans.add(a[i]);
                }
            }

            ans.add(a[n-1]);
            printL(ans.size());
            for(int i:ans){
                System.out.print(i+" ");
            }

            System.out.println();
       }
    }




 

    

    //xor range query
    static long xor(long n)
    {

        if(n%4==0)
        {
            return n;
        }
        if(n%4==1)
        {
            return  1;
        }
        if(n%4==2)
        {
            return n+1;
        }
        return 0;
    }

    static long xor(long a,long b)
    {
        return xor(b)^xor(a-1);
    }


    

  
   
    

    
       
    

    
   
  



   

     void printL(long a)
    {
        System.out.println(a);
    }
    void printS(String s)
    {
        System.out.println(s);
    }

     void printD(Double d)
    {
        System.out.println(d);
    }
  
   
   
    static void swap(char c,char p)
    {
        char t = c;
        c = p;
        p = t;
    }

    static long max(long n,long m)
    {
        return Math.max(n,m);
    }
    static long min(long n,long m)
    {
        return Math.min(n,m);
    }

    double nd() throws IOException
    {
        return Double.parseDouble(in.next());
    }
    int ni() throws IOException
    {
        return Integer.parseInt(in.next());
    }

    long nl() throws IOException
    {
        return Long.parseLong(in.next());
    }

    String si() throws IOException
    {
        return in.next();
    }


  
   
    static int abs(int n)
    {
        return Math.abs(n);
    }

    static class Scanner 
    {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream s){  br = new BufferedReader(new InputStreamReader(s));}

        public String next() throws IOException 
        {
            while (st == null || !st.hasMoreTokens()) 
            {
                st = new StringTokenizer(br.readLine());
            }
            return st.nextToken();
        }

        public int nextInt() throws IOException {return Integer.parseInt(next());}
        
        public long nextLong() throws IOException {return Long.parseLong(next());}

        public String nextLine() throws IOException {return br.readLine();}

        public boolean ready() throws IOException {return br.ready();}


    }

    
}



class Pair implements Comparable<Pair>
{
   int x,y;
    public Pair(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
    public int compareTo(Pair o)
    {
        return this.y-o.y;
    }
}