gard

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ţă

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 $H_i$ 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 \leq T \leq 10$;
• Primele 50% din teste:
  • $1 \leq N \leq 1 \ 000 \ 000$;
  • $1 \leq H_i \leq 10 \ 000$.
• Următoarele 50% din teste:
  • $1 \leq N \leq 100 \ 000$;
  • $1 \leq H_i \leq 1 \ 000 \ 000 \ 000$.
• Pentru 50% din totalul testelor, eliminarea oricărei scânduri nu va transforma un gard imperfect într-unul perfect.

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.