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:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f

def make_next(n, nums):
    imos = [0 for i in range(n)]
    for i, num in enumerate(nums):
        if num > i:
            imos[0] += 1
        else:
            imos[i - num] += 1

        if i + num + 1 < n:
            imos[i+num+1] -= 1
    # print(imos)
    nx = []
    tmp = 0
    for im in imos:
        tmp += im
        nx.append(tmp)

    return nx

def mantan_check(n, nums):
    if sum(nums) == n ** 2:
        return True
    else:
        return False
def knapsack(tree, vx, l):
    dp = [0 for i in range(l + 1)]
    while True:
        dpcp = copy.copy(dp)
        v, w = tree[vx-1]
        # print(v, w)
        for i, d in enumerate(dp):
            if w + i < l + 1:
                if dpcp[w + i] < v + d:
                    dpcp[w + i] = v + d
        dp = copy.copy(dpcp)
        vx //= 2
        dp = dpcp
        # print(dp)
        if vx == 0:
            break

    return max(dp)

def solve():
    n = getN()
    nums = getList()
    ans = [nums[0]]
    if n == 2:
        print(n)
        print(*nums)
        return

    prev = nums[1]
    if nums[0] < nums[1]:
        up = True
    else:
        up = False

    for num in nums[2:]:
        if prev < num:
            cup = True
        else:
            cup = False

        if up != cup:
            ans.append(prev)

        up = cup
        prev = num

    ans.append(nums[-1])
    print(len(ans))
    print(*ans)
    return

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    main()

"""
5 10000000000000
4 0 0 0 0
"""