Alice 收到了一串由邻居给出的序列 $A$。由于 Alice 不喜欢过长的序列，她决定将该序列划分为两个（可能为空的）序列 $B$ 和 $C$，并将它们归还给邻居。她的划分需要满足以下约束：

• $B$ 和 $C$ 均为序列 $A$ 的子序列。
• $A$ 中的每个元素恰好属于序列 $B$ 或 $C$ 中的一个。
• 在字典序上，$B \le C$。

在此，我们定义一个长度为 $u$ 的序列 $P = p_1, p_2, \dots, p_u$ 在字典序上小于长度为 $v$ 的序列 $Q = q_1, q_2, \dots, q_v$，如果满足以下任一条件：

• $u < v$ 且 $P$ 是 $Q$ 的前缀。
• 存在一个整数 $1 \le k \le \min(u, v)$，使得对于所有 $1 \le i < k$ 有 $p_i = q_i$，且 $p_k < q_k$。

作为一个公平的女孩，Alice 希望进行公平的划分，使得 $C$ 的字典序尽可能小。请告诉 Alice $C$ 可能的最小值。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^3$)，表示序列 $A$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$)，其中 $a_i$ 是序列 $A$ 的第 $i$ 个元素。

保证所有测试数据的 $n$ 之和不超过 $10^4$。

输出格式

对于每组测试数据，输出两行。第一行输出一个整数 $m$，表示最优序列 $C$ 的长度。第二行输出 $m$ 个整数 $c_1, c_2, \dots, c_m$，中间用空格隔开，其中 $c_i$ 是最优序列 $C$ 的第 $i$ 个元素。

样例

输入 1

5
5
3 1 2 3 2
3
1 1 2
3
3 3 3
5
1 3 1 3 1
5
2 2 1 3 3

输出 1

1
3
3
1 1 2
2
3 3
3
1 3 1
4
2 1 3 3