Mihăiță s-a hotărât să își construiască un gard perfect cu ajutorul lui Dorel – un constructor renumit.
Un gard perfect trebuie să respecte următoarele cerințe:
1. Gardul să fie format din N scânduri de înălțimi nu neapărat egale;
2. Scândurile pot fi așezate în orice ordine;
3. Există un număr egal de scânduri pentru fiecare înălțime;
Mihăiță acceptă un gard ca fiind perfect dacă respectă condițiile de mai sus înainte sau după eliminarea unei singure scânduri.

Cerința

Ajutați-l pe Mihăiță să verifice perfecțiunea celor T garduri propuse de Dorel.

Date de intrare

Pe prima linie din fișierul gard.in se află un număr natural T, reprezentând numărul gardurilor propuse de Dorel. Pe următoarele T linii se află un număr natural N, urmat de N valori Hi separate printr-un singur spațiu, reprezentând înălțimile scândurilor gardului propus de Dorel.

Date de ieșire

Fișierul de ieșire gard.out va conține T linii, pe fiecare linie fiind afișat 1 dacă gardul este perfect, 0 altfel.

Restricții și precizări

• 1 ≤ T ≤ 10
• Primele teste, 1 ≤ N ≤ 1.000.000, 1 ≤ Hi ≤ 10.000
• Următoarele teste, 1 ≤ N ≤ 100.000, 1 ≤ Hi ≤ 1.000.000.000
• Datorită dimensiunii mari ale testelor, doar unele dintre ele au fost încărcate.

Exemplu:

gard.in

4
6 2 2 3 3 4 4
6 2 3 3 5 5 5
7 3 3 4 4 4 5 5
8 3 3 3 4 4 5 5 5

gard.out

1
0
1
0

Explicație

1: Există un număr egal de scânduri pentru fiecare înălțime
0: Gardul nu poate fi perfect nici înainte și nici după eliminarea oricărei scânduri
1: Gardul devine perfect după eliminarea unei scânduri de înălțime 4
0: Gardul nu poate fi perfect nici înainte și nici după eliminarea oricărei scânduri