Alice and Bob have $2n$ cards, each with an integer written on it, such that each integer between $1$ and $n$ appears on exactly two cards. Initially, Alice and Bob each hold $n$ cards.

They are going to play a card game, with Alice going first. On each turn, the current player places a card from their hand on top of the pile. If there are now two cards with the same number in the pile, the current player scores $1$ point and removes the two matching cards along with all cards in between, placing them in the discard pile.

Given Alice's sequence of moves, how can Bob arrange his moves to minimize Alice's score?

Input

The first line contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases.

For each test case, the first line contains an integer $n$ ($1 \le n \le 5 \times 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), representing the numbers on the cards played by Alice in order. It is guaranteed that no number appears more than twice in $a_i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \times 10^5$.

Output

For each test case, the first line of output should contain an integer, representing the minimum score Alice can get.

The second line should contain $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), representing Bob's moves in order, such that each integer from $1$ to $n$ appears exactly twice in the combined sequences of $a_i$ and $b_i$.

Example

Input

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

Output

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

Note

For the third test case, the game proceeds as follows: