Alice 和 Bob 正在玩一个卡牌游戏。他们收集了 $2n$ 张卡牌，每张卡牌上都写有一个整数。此外，介于 $1$ 到 $n$ 之间的每个整数都恰好出现两次。最初，Alice 和 Bob 各持有 $n$ 张卡牌。

游戏将轮流进行，Alice 先手。在每个回合中，当前玩家必须从手牌中选择一张卡牌并将其放在牌堆顶部。如果此时牌堆中出现了两张写有相同数字的卡牌，当前玩家获得 1 分，并将这两张匹配的卡牌以及它们之间的所有卡牌移出牌堆，放入弃牌堆。

Alice 是这个游戏的新手，Bob 想捉弄她。Bob 想知道：对于给定的 Alice 的出牌序列，他应该如何安排自己的出牌顺序，以使 Alice 的得分最小？

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)，表示不同卡牌种类的数量。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示 Alice 的出牌序列。保证在序列 $a_i$ 中，没有任何数字出现超过两次。

保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例：

第一行输出一个整数，表示 Alice 的最小得分。

第二行输出 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$)，表示 Bob 的出牌序列之一。必须确保从 $1$ 到 $n$ 的每个数字在 $a_i$ 和 $b_i$ 的合并序列中恰好出现两次。如果有多个序列能使 Alice 的得分最小，输出其中任意一个即可。

样例

输入样例 1

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

输出样例 1

0
1 2 3
0
2 3 2 4 5
1
3 2 2 3 5

说明

对于第三个测试用例，每轮操作对应的事件以及每次操作后牌堆的状态如下：