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:
//package cp;
import java.util.*;

import static java.lang.Math.min;
import static java.lang.Math.abs;
import static java.lang.Math.max;
import java.io.*;
import java.text.DateFormatSymbols;
 
public class Codechef {
	static long[] mods = {1000000007, 998244353, 1000000009};
	static long mod = mods[0];
	public static MyScanner in;
    public static PrintWriter out;
    static int[][] dp;
    public static ArrayList<Long> primeFactors=new ArrayList<>();
    
	public static void main( String[] args ) throws IOException{
		
 		in = new MyScanner();	
 		out = new PrintWriter(System.out);
 		StringBuilder ans1=new StringBuilder(); 
		int test=in.nextInt();
		while(test-->0) {
			StringBuilder ans=new StringBuilder();
			int n=in.nextInt();
			long arr[]=readArrayLong(n);
			ArrayList<Long> a=new ArrayList<>();
			
			for(int i=0;i<n;i++){
			     if(i==0 || i==n-1 || (arr[i]>arr[i-1] && arr[i]>arr[i+1]) || (arr[i]<arr[i-1] && arr[i]<arr[i+1])){
			          //diff+=((long)Math.abs(arr[i]-arr[i-1]));
			          a.add(arr[i]);
			     }
			}
			
			ans.append(a.size()).append("\n");
			for(long i: a) ans.append(i+" ");
			
			ans1.append(ans).append(System.getProperty("line.separator"));
		}
		
		out.println(ans1);
 		out.close();
 		
 	}

	//sorted check in non decreasing order
	static boolean isSorted(long arr[], int n){
       if (n == 0 || n == 1)      return true;
       for (int i = 1; i < n; i++)
           if (arr[i - 1] > arr[i])    return false;
       return true;
    }
	
	public static void primeFactorization(long n){
        while (n%2==0){
            primeFactors.add((long) 2);
            n /= 2;
        }
        for (int i = 3; i <= Math.sqrt(n); i+= 2){
            while (n%i == 0){
                primeFactors.add((long) i);
                n /= i;
            }
        }
        if (n > 2)	primeFactors.add((long)n);
    }
	
	static long lcm_comp(long a, long b) {	return (a / gcd_comp(a, b)) * b;	}
 
	static long gcd_comp(long a, long b){
        if (a == 0)		return b;
        if (b == 0)		return a;
        long k;
        for (k = 0; ((a | b) & 1) == 0; ++k){
            a >>= 1;
            b >>= 1;
        }
        while ((a & 1) == 0)	a >>= 1;  
        do{
            while ((b & 1) == 0)	 b >>= 1;
            if (a > b){    
                long temp = a;
                a = b;
                b = temp;
            }
            b = (b - a);
        } while (b != 0);
        return a << k;
    }

	
	//comparator to solve according to b in descending order
	static class Pair implements Comparable<Pair>{
		private long a;
		private long b;
		public Pair(long a, long b) {
			this.a = a;
			this.b = b;
		}
		public int compareTo(Pair other) {
			return Long.compare(this.b, other.b );		//to sort in ascending order swap the arguments in Long.compare
			//return Long.compare(other.b ,this.b); 	//to sort in descending order swap the arguments in Long.compare
		}
	}
	
	static void printArray(long[] a) {
		StringBuilder stringBuilder=new StringBuilder();
		for(long i: a)	stringBuilder.append(i).append(" ");
		out.println(stringBuilder);
	}
	
	static void printArray(int[] a) {
		StringBuilder stringBuilder=new StringBuilder();
		for(int i: a)	stringBuilder.append(i).append(" ");
		out.println(stringBuilder);
	}
	
	public static void sort(long[] array){
		ArrayList<Long> copy = new ArrayList<>();
		for (long i : array)
			copy.add(i);
		Collections.sort(copy);
		for(int i = 0;i<array.length;i++)
			array[i] = copy.get(i);
	}
	
	public static void sortDes(long[] array){
		ArrayList<Long> copy = new ArrayList<>();
		for (long i : array)
			copy.add(i);
		Collections.sort(copy);
		int j=array.length-1;
		for(int i = 0;i<array.length;i++)
			array[j--] = copy.get(i);
	}
	
	
	static String[] readArrayString(int n){
		String[] array = new String[n];
		for(int j =0 ;j<n;j++)
			array[j] = in.next();
		return array;
	}
	
	
	static int[] readArrayInt(int n){
    	int[] array = new int[n];
    	for(int j = 0;j<n;j++)
    		array[j] = in.nextInt();
    	return array;
    }
	
	static int[] readArrayInt1(int n){
		int[] array = new int[n+1];
		for(int j = 1;j<=n;j++){
			array[j] = in.nextInt();
		}
		return array;
	}
	
	static long[] readArrayLong(int n){
		long[] array = new long[n];
		for(int j =0 ;j<n;j++)
			array[j] = in.nextLong();
		return array;
	}
	
	static double[] readArrayDouble(int n){
		double[] array = new double[n];
		for(int j =0 ;j<n;j++)
			array[j] = in.nextDouble();
		return array;
	}
	
	static int minIndex(int[] array){
		int minValue = Integer.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	
	static int minIndex(long[] array){
		long minValue = Long.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	
	static int minIndex(double[] array){
		double minValue = Double.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	
	
	static int maxIndex(int[] array){
		int maxValue = Integer.MIN_VALUE;
		int maxIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] > maxValue){
				maxValue = array[j];
				maxIndex = j;
			}
		}
		return maxIndex;
	}
	
	static int maxIndex(long[] array){
		long maxValue = Long.MIN_VALUE;
		int maxIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] > maxValue){
				maxValue = array[j];
				maxIndex = j;
			}
		}
		return maxIndex;
	}
	
	
	static long power(long x, long y){
		if (y == 0)
			return 1;
		if (y%2 == 1)
			return (x*power(x, y-1))%mod;
		return power((x*x)%mod, y/2)%mod;
	}
	static void verdict(boolean a){
        out.println(a ? "YES" : "NO");
    }
	
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } 
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } 
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
    }	
}