Alice og Bob eru með $2n$ spil, hvert með heiltölu skrifaða á sig, þannig að hver heiltala á bilinu $1$ til $n$ kemur fyrir á nákvæmlega tveimur spilum. Í upphafi halda Alice og Bob á $n$ spilum hvort.

Þau ætla að spila spilaleik og Alice gerir fyrst. Í hverri umferð leggur leikmaðurinn sem á leik eitt spil úr hendi sér efst á bunkann. Ef það eru nú tvö spil með sömu tölu í bunkanum fær leikmaðurinn $1$ stig og fjarlægir bæði samstæðu spilin ásamt öllum spilum á milli þeirra og setur þau í ruslabunkann.

Ef röð leikja Alice er gefin, hvernig getur Bob raðað sínum leikjum til að lágmarka stigafjölda Alice?

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^5$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan heiltölu $n$ ($1 \le n \le 5 \times 10^5$).

Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), sem tákna tölurnar á spilunum sem Alice spilar í röð. Tryggt er að engin tala kemur fyrir oftar en tvisvar í $a_i$.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $5 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal fyrsta lína úttaksins innihalda heiltölu sem táknar lágmarksstigafjölda sem Alice getur fengið.

Önnur línan skal innihalda $n$ heiltölur $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$), sem tákna leiki Bobs í röð, þannig að hver heiltala frá $1$ til $n$ komi fyrir nákvæmlega tvisvar í sameinuðum runum $a_i$ og $b_i$.

Dæmi

Inntak

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

Úttak

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

Athugasemd

Fyrir þriðja prófunartilvikið gengur leikurinn fyrir sig sem hér segir: