Alice och Bob har $2n$ kort, vart och ett med ett heltal skrivet på sig, så att varje heltal mellan $1$ och $n$ förekommer på exakt två kort. Från början håller Alice och Bob $n$ kort var.

De ska spela ett kortspel, där Alice börjar. Under varje drag lägger den aktuella spelaren ett kort från sin hand överst i högen. Om det nu finns två kort med samma tal i högen får den aktuella spelaren $1$ poäng och tar bort de två matchande korten tillsammans med alla kort däremellan, och lägger dem i skräphögen.

Givet Alices sekvens av drag, hur kan Bob ordna sina drag för att minimera Alices poäng?

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 10^5$), som anger antalet testfall.

För varje testfall innehåller den första raden ett heltal $n$ ($1 \le n \le 5 \times 10^5$).

Den andra raden innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), som representerar talen på de kort som Alice spelar i ordning. Det garanteras att inget tal förekommer mer än två gånger i $a_i$.

Det garanteras att summan av $n$ över alla testfall inte överstiger $5 \times 10^5$.

Utdata

För varje testfall ska den första raden i utdata innehålla ett heltal, som representerar den minsta poäng Alice kan få.

Den andra raden ska innehålla $n$ heltal $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), som representerar Bobs drag i ordning, så att varje heltal från $1$ till $n$ förekommer exakt två gånger i de kombinerade sekvenserna av $a_i$ och $b_i$.

Exempel

Indata

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

Utdata

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

Notering

För det tredje testfallet fortskrider spelet enligt följande: