Програмчлалын олимпиадын бодлогын архив

2 тоглогч дараах тоглоомыг тоглоно. N ширхэг багц байгаа i-р багцанд a_i ширхэг багц байгаа(1<=i<=N) . Тэгвэл тоглоом дараах дүрэмтэй:
Хоосон биш нэг багцыг сонгоод зөвхөн түүнээсээ дор хаяж нэг саваа сугалж хаяна.
2 тоглогч ээлжлэн тоглосоор өөрийнхөө ээлжинд саваа авах боломжгүй болсон тоглогч хожигдоно(Авах гэтэл бүх багц хоосорсон тохиолдолд) 2 тоглогч 2 - уулаа хамгийн зөв стратегиэр тоглох бол аль тоглогч хожихыг олно уу?
Хязгаарлалт : 1<=N<=10^5 1<=t<=20 1<=a_i<=20000

Input

Эхний мөрөнд тестийн тоо “t"
Дараагийн “t” мөрөнд :
Эхний мөрөнд тоо N байрлана. Тэгээд a_i (1<=i<=N ) тоонууд хоосон зайгаар тусгаарлагдан байрлана

Output

“t” мөрөөс тогтох ба
Эхний тоглогч хожих бол 1
Эхний тоглогч хожигдох бол 0 гэж гаргана

Example

Input:
2
1 2
2 2


Output:
1
0

Ц. Дүүрэнбаярын нэрэмжит олимпиад - 2008 он.