eolymp
Competitions

XIII Всеукраинская олимпиада по информатике, Киев, Март 27 - Апрель 1, 2000

Последовательность

Дана последовательность, состоящая из 2N натуральных чисел. Известно, что все числа этой последовательности можно разбить на пары таким образом, что сумма чисел во всех парах будет одинаковой. Например, числа последовательности 99, 23, 77, 1 можно разбить на пары 1 + 99 = 77 + 23.

Напишите программу, которая по такой последовательности определяет, можно ли эту последовательность разбить на пары таким образом, чтобы произведение чисел во всех парах было одинаковым.

Входные данные

Первая строка содержит количество тестов. Первая строка каждого теста содержит количество чисел 2N (1 N 50000) в последовательности. В каждой из последующих 2N строчек содержится целое число от 1 до 109 - элементы последовательности.

Выходные данные

Для каждого теста в отдельной строке вывести символ 1, если входную последовательность можно разбить на пары, произведения в которых были бы одинаковыми, и 0 в противном случае.

Time limit 0.5 seconds
Memory limit 64 MiB
Input example #1
2
4
99
23
77
1
2
1
10101
Output example #1
0
1
Source 2000 XIII All-Ukrainian Informatics Olympiad, Kiev, March 27 - April 1, Round 1