eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

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

Giriş verilənləri

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

1 <= N <= 10^3

1 <= S_i <= 10^6

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2
3
2 2 3
2
3 3
Çıxış verilənləri #1
12