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:

/*
		Idea:
I think just keep taking greedily elements should work here .
As we know element are distinct here so we can keep taking greedily peak and valley elements.
*/
import java.util.*;
import java.io.*;
import java.lang.*;
import java.math.BigInteger;

public class A {

static FastReader		sc	= new FastReader();
static PrintWriter	out	= new PrintWriter(System.out);

public static void main(String[] args) throws Exception {
//	try {
	fact=new long[100005];
	fact[0]=1;
	for(int i=1;i<=100004;i++) {
		fact[i]=(fact[i-1]*i)%mod;
	}
	invfact=new long[100005];
	invfact[0]=1;
	for(int i=1;i<100005;i++) {
		invfact[i]=pow(fact[i],mod-2);
	}
int t=sc.nextInt();
while(t-->0) {
	A.go();
}
out.flush();
//	} catch (Exception e) {
//		return;
//	}
}

//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Code Starts <<<<<<<<<<<<<<<<<<<<<<<<<<<<< //

static void swap(int a[],int i,int j) {
	a[i]=a[i]^a[j];
	a[j]=a[j]^a[i];
	a[i]=a[i]^a[j];
}

static void go() {
	int n=sc.nextInt();
	int a[]=new int[n];
	for(int i=0;i<n;i++) {
		a[i]=sc.nextInt();							
		}													

int i=0;
ArrayList<Integer>ans=new ArrayList<>();
boolean vis[]=new boolean[n+1];
int j =0;
ans.add(a[i]);
while(i<n && j<n) {

j=i+1;
int prev=0;
int ele=a[i];

if(a[j]>ele) {
while(j<n && a[j]>ele) {
ele=a[j];
j++;
}
}else {
while(j<n && a[j]<ele) {
	ele=a[j];
	j++;
}
}
if(ele!=0)
ans.add(ele);
i=j-1;
}
out.println(ans.size());
for(int k:ans) {
	out.print(k+" ");
}
out.println();
	
}


static void   print(long a[][]) {
	out.println("--------");
	for(int i=0;i<a.length;i++) {
		for(int j=0;j<a[i].length;j++) {
			out.print(a[i][j]+" ");
		}
		out.println();
	}
}
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Code Ends <<<<<<<<<<<<<<<<<<<<<<<<<<<<< //
static long fact[];
static long invfact[];
static long ncr(int n,int k) {
	if(k<0||k>n) {
		return 0;
	}
	long x=fact[n]%mod;
	long y=invfact[k]%mod;
	long yy=invfact[n-k]%mod;
	long ans=(x*y)%mod;
	ans=(ans*yy)%mod;
	return ans;
}
static long gcd(long a, long b) {
	if (b==0) {
		return a;
	}return gcd(b, a%b);
}
static int	prime[]	= new int[200005];
static int	N				= 200005;
static void sieve() {

	for(int i=0;i<N;i++) {
		prime[i]=i;
}
	for (int i = 2; i * i <= N; i++) {
		if (prime[i] == i) {
			prime[i]=i;
			for (int j = i; j < N; j += i) {
				prime[j] =i;
			}}}
}


static int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}return gcd(b, a % b);
}
 static void sort(int[] a) {
	ArrayList<Integer> aa = new ArrayList<>();
	for (Integer i : a) {
		aa.add(i);	}
	Collections.sort(aa);
	for (int i = 0; i < a.length; i++)
		a[i] = aa.get(i);}
static void sort(long[] a) {
	ArrayList<Long> aa = new ArrayList<>();
	for (Long i : a) {
		aa.add(i);}
	Collections.sort(aa);
	for (int i = 0; i < a.length; i++)
		a[i] = aa.get(i);
}

static int mod = (int) 1e9 + 7;

static long pow(long x, long y) {
	long res = 1l;
	while (y != 0) {
		if (y % 2 == 1) {
			res = (x%mod * res%mod)%mod;
			}	y /= 2;
			x = (x%mod * x%mod)%mod;
	}
	return res%mod;
}


//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Fast IO <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< //

static class FastReader {
	BufferedReader	br;
	StringTokenizer	st;
	public FastReader() {
		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;
	}	}}
class interval implements Comparable<interval>{
	long x,y;
	interval(long x,long y){
		this.x=x;this.y=y;
	}
	@Override
	public int compareTo(interval o) {
		if(o.x==this.x) {
			return Long.compare(o.y,this.y);
		}
		return -Long.compare(o.x, this.x);
	}
}