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 PYTHON3):

Solution:
from fractions import Fraction
import bisect
import os
import io
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq as hq
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations
from io import BytesIO, IOBase
from itertools import accumulate
from queue import Queue


# sys.setrecursionlimit(200000)
# input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


def input():
    return sys.stdin.readline().strip()


def iinput():
    return int(input())


def tinput():
    return input().split()


def rinput():
    return map(int, tinput())


def rlinput():
    return list(rinput())


mod = int(1e9)+7


def factors(n):
    return set(reduce(list.__add__,
                      ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))


# ----------------------------------------------------
# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')
t = 1
t = iinput()
for _ in range(t):
    n = iinput()
    a = rlinput()
    # mintill = [0]*n
    # maxtill =  [0]*n
    d = defaultdict(int)
    for i in range(n):
        d[a[i]] = i
    # mintill[0],maxtill[0]=a[0],a[0]
    # for i in range(1,n):
    #     mintill[i] = min(mintill[i-1],a[i])
    #     maxtill[i] = max(maxtill[i-1],a[i])
    # ans = []
    # i = n-1
    # print(maxtill,mintill)
    # while i!=0:
    #     val1 = abs(a[i]-mintill[i])
    #     val2 = abs(a[i]-maxtill[i])
    #     if val1 > val2:
    #         ans.append(a[i])
    #         i = d[mintill[i]]
    #     elif val1 < val2:
    #         ans.append(a[i])
    #         i = d[maxtill[i]]
    #     else:
    #         ans.append(a[i])
    #         i = min(d[mintill[i]],d[maxtill[i]])
    #     if i==0:
    #         break
    # ans.append(a[0])
    # print(len(ans))
    # print(*ans[::-1])
    ans = [a[0]]
    i = 1
    while i < n:
        j = i
        while j < n and a[j] > a[j-1]:
            j += 1
        if i != j and j<n:
            ans.append(a[j-1])
        elif j==n:
            ans.append(a[j-1])
        # print(ans,j)
        k = j
        while k < n and a[k] < a[k-1]:
            k += 1
        if j != k and k<n:
            ans.append(a[k-1])
        elif k==n and j!=n:
            ans.append(a[k-1])
        i = k
    print(len(ans))
    print(*ans)