Разделить или забрать?

Есть N кучек с камешками. За один ход разрешается либо забрать любое количество камешков из одной кучки, либо разделить кучку на две более мелкие. Побеждает тот, кто забирает последний камешек.

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

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

В первой строке задано количество тестовых случаев T (1 <= T <= 100) Далее следует T пар строк, в первой из которых находится значение N, а во второй через пробел количества камушков в каждой из кучек S_i.

1 <= N <= 10^3

1 <= S_i <= 10^6

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

Единственная строка, состоящая из последовательности 1 и 2 - номера победивших игрока.

Примеры