Зертханада \(n\) модуль бар, әр модульде \(a_i\) саны жазылған. Сіз оларды белгілі бір ретпен тізбекке қоясыз. Жүйе ағымдағы кодты жүргізеді — тізбекке қойылған модульдердің барлығының XOR-ы.

• Бастапқыда ағымдағы код \(0\)-ге тең.

• Келесі модульдің мәні \(x\) болса, ағымдағы код былай жаңартылады: \(\text{code} \leftarrow \text{code} \oplus x\).

• Егер жаңартудан кейін ағымдағы код \(0\) болса, триггер іске қосылады.

Сіз модульдерді қалағаныңызша орындарын ауыстыра аласыз. Талап: триггердің іске қосылу саны (яғни префикстік XOR нөлге тең болатын индекстер саны) мүмкін болғанша ең аз болатындай кез келген модульдер ретін шығарыңыз.

Формалды түрде, орын ауыстырғаннан кейін \(p\) массивін (яғни \(a\) элементтерінің перестановкасын) аламыз. Префикстік XOR-ларды анықтайық: \[\mathrm{pref}_i = p_1 \oplus p_2 \oplus \dots \oplus p_i \quad (1 \le i \le n),\] мұндағы \(\oplus\) — биттік XOR операциясы.

Міндет: \(\mathrm{pref}_i = 0\) болатын \(i\) индекстер саны минимал болатындай \(p\) перестановкасын шығару.

Енгізу

Бірінші жолда \(t\) — тесттер саны берілген.

Әрі қарай \(t\) тест берілген. Әр тест үшін:

• бірінші жолда \(n\) бүтін саны берілген (\(1 \le n \le 2 \cdot 10^5\));

• екінші жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) берілген (\(0 \le a_i < 2^{30}\)).

Барлық тесттер бойынша \(n\)-нің қосындысы \(2 \cdot 10^5\)-тен аспайды.

Шығару

Әр тест үшін бір жолға \(n\) сан шығарыңыз: \(p_1, p_2, \dots, p_n\) — \(a\) массивінің элементтерінен құралған перестановка, мұнда \(\mathrm{pref}_i = 0\) болатын \(i\) индекстер саны минимал.

Егер бірнеше жауап болса, кез келгенін шығарыңыз.

Мысалдар

Енгізу 1

5
4
0 0 0 0
3
1 2 3
5
3 0 6 7 0
3
6 4 2
8
0 1 2 3 4 5 6 7

Жауап 1

0 0 0 0
2 1 3
3 6 7 0 0
4 6 2
1 2 4 5 6 3 0 7