У Аліси та Боба є $2n$ карт, на кожній із яких написано ціле число, причому кожне ціле число від $1$ до $n$ зустрічається рівно на двох картах. Спочатку в Аліси та Боба на руках по $n$ карт.

Вони збираються зіграти в карткову гру; першою ходить Аліса. У кожен хід поточний гравець кладе карту зі своєї руки наверх стопки. Якщо після цього в стопці опиняються дві карти з однаковим числом, поточний гравець отримує $1$ бал і забирає ці дві однакові карти разом з усіма картами між ними, відправляючи їх у відбій.

Знаючи послідовність ходів Аліси, як Бобу спланувати свої ходи, щоб мінімізувати кількість балів Аліси?

Вхідні дані

Перший рядок містить ціле число $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$) — числа на картах, які по черзі викладає Аліса. Гарантується, що жодне число не зустрічається в $a_i$ більше ніж двічі.

Гарантується, що сума $n$ за всіма наборами вхідних даних не перевищує $5 \times 10^5$.

Вихідні дані

Для кожного набору вхідних даних у першому рядку виведіть одне ціле число — мінімальну кількість балів, яку може набрати Аліса.

У другому рядку виведіть $n$ цілих чисел $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), що позначають ходи Боба по черзі, так, щоб кожне ціле число від $1$ до $n$ зустрічалося рівно двічі в об'єднаних послідовностях $a_i$ та $b_i$.

Приклад

Вхідні дані

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

Вихідні дані

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

Примітка

У третьому наборі вхідних даних гра відбувається таким чином: