Алиса мен Бобта әрқайсысында бүтін сан жазылған $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$ мәнінен аспайтынына кепілдік беріледі.
Шығыс деректер
Әрбір тест үшін шығыстың бірінші жолында Алиса жинай алатын ең аз ұпайды білдіретін бүтін сан болуы керек.
Екінші жолда $1$-ден $n$-ге дейінгі әрбір бүтін сан $a_i$ мен $b_i$ біріктірілген тізбектерінде дәл екі рет кездесетіндей етіп, Бобтың ретімен жасаған жүрістерін білдіретін $n$ бүтін сан $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$) болуы керек.
Мысал
Кіріс деректер
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
Ескертпе
Үшінші тест үшін ойын келесідей өтеді:
| Қадам | Ойыншы | Ойналған карта | Төменнен жоғарыға қарай үйінді | Алисаның ұпайы | Бобтың ұпайы |
|---|---|---|---|---|---|
| $1$ | Алиса | $1$ | $[1]$ | $0$ | $0$ |
| $2$ | Боб | $3$ | $[1, 3]$ | $0$ | $0$ |
| $3$ | Алиса | $4$ | $[1, 3, 4]$ | $0$ | $0$ |
| $4$ | Боб | $2$ | $[1, 3, 4, 2]$ | $0$ | $0$ |
| $5$ | Алиса | $5$ | $[1, 3, 4, 2, 5]$ | $0$ | $0$ |
| $6$ | Боб | $2$ | $[1, 3, 4]$ | $0$ | $1$ |
| $7$ | Алиса | $1$ | $[]$ | $1$ | $1$ |
| $8$ | Боб | $3$ | $[3]$ | $1$ | $1$ |
| $9$ | Алиса | $4$ | $[3, 4]$ | $1$ | $1$ |
| $10$ | Боб | $5$ | $[3, 4, 5]$ | $1$ | $1$ |