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].
#include <bits/stdc++.h>
using namespace std;
namespace AC {
const long long N = 1e5 + 66;
long long BUGS = 1;
inline long long read() {
  long long x = 0;
  bool flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = 0;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = (x << 1) + (x << 3) + ch - '0';
    ch = getchar();
  }
  if (flag) return x;
  return (~(x - 1));
}
inline void read(long long arr[], long long s, long long e) {
  for (long long i = s; i <= e; ++i) arr[i] = read();
}
inline void write(long long x) {
  if (x < 0) {
    x = ~(x - 1);
    putchar('-');
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline void print(long long x) {
  write(x);
  puts("");
}
inline void print(long long arr[], long long s, long long e) {
  for (long long i = s; i <= e - 1; ++i) write(arr[i]), putchar(' ');
  write(arr[e]);
  puts("");
}
inline long long max3(long long a, long long b, long long c) {
  return max(a, max(b, c));
}
inline long long min3(long long a, long long b, long long c) {
  return min(a, min(b, c));
}
inline void debugNum(long long num, string ss) {
  cout << "BUGS" << BUGS++ << " : " << ss << " : " << num << endl;
}
inline void debugArr(long long arr[], long long s, long long e, string ss) {
  cout << "BUGS" << BUGS++ << " : " << ss << " : " << endl;
  for (long long i = s; i <= e; ++i)
    cout << "i : " << i << " val : " << arr[i] << endl;
}
inline void IO() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
}
}  // namespace AC
using namespace AC;
long long n, arr[N];
bool use[N];
int main() {
  long long T = read();
  while (T--) {
    n = read(), read(arr, 1, n);
    for (long long i = 1; i <= n; ++i) {
      use[i] = false;
    }
    use[1] = use[n] = true;
    for (long long i = 2; i < n; ++i) {
      if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) use[i] = true;
      if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1]) use[i] = true;
    }
    long long ans = 0;
    for (long long i = 1; i <= n; ++i) {
      if (use[i] == true) ans++;
    }
    print(ans);
    for (long long i = 1; i <= n; ++i) {
      if (use[i] == true) printf("%lld ", arr[i]);
    }
    puts("");
  }
  return 0;
}
