Tema 和 Vika 在玩一个游戏。

首先，Vika 想出一个由正整数组成的序列 $a$，长度为 $m$，并写在纸上。接着她在另一张纸上按如下规则写出序列 $b$：

1. 先写下 $a_1$。
2. 对于 $2 \le i \le m$，仅当 $a_{i-1} \le a_i$ 时，才把 $a_i$ 写入序列 $b$。

记得到的序列 $b$ 的长度为 $n$。

例如，若 $a=[4,3,2,6,3,3]$，则得到 $b=[4,6,3]$。

随后她把写有序列 $b$ 的纸交给 Tema，Tema 试图猜测原序列 $a$。Tema 觉得获胜很难，但他希望至少能找到一种可能的序列 $a$ 作为答案。请你帮助他输出任意一种满足条件的序列 $a$。

注意：你输出的序列长度必须满足 $n \le m \le 2n$（即不超过输入序列长度的两倍）。

输入格式

输入包含多组测试用例。

• 第一行一个整数 $t$（$1 \le t \le 10^4$）表示测试用例数量。

• 每个测试用例：

  • 第一行一个整数 $n$（$1 \le n \le 2\cdot 10^5$）表示序列 $b$ 的长度；
  • 第二行 $n$ 个整数 $b_1,b_2,\dots,b_n$（$1 \le b_i \le 10^9$）表示序列 $b$。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

输出格式

对每个测试用例输出两行：

1. 第一行输出一个整数 $m$（$n \le m \le 2n$）表示你构造的序列 $a$ 的长度；
2. 第二行输出 $m$ 个正整数 $a_1,a_2,\dots,a_m$（$1 \le a_i \le 10^9$）表示你构造的序列 $a$。

本题允许输出任意一种满足条件的序列。为保证本平台“固定输入输出”的数据生成一致性，本文固定采用如下构造输出：

• 令 $a_1=b_1$；

• 对于 $i=2..n$：

  • 若 $b_{i-1}\le b_i$，则在 $a$ 末尾追加 $b_i$；
  • 否则在 $a$ 末尾依次追加 $1$、$b_i$。

该构造保证输出唯一且满足 $n \le m \le 2n$。

样例

输入

6
3
4 6 3
3
1 2 3
5
1 7 9 5 7
1
144
2
1 1
5
1 2 2 1 1

输出（其中一种）

6
4 3 2 6 3 3
3
1 2 3
6
1 7 9 3 5 7
1
144
2
1 1
6
1 2 2 1 1 1