Задача B. Ним с делением

Автор:Туфанов И.   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Формат входного файла

Во входном файле содержится число N — количество Ним-куч. Далее следует N чисел ai — величина каждой кучи.

Формат выходного файла

В выходной файл выведите число 1, если выиграет первый игрок, 2 — если выиграет второй.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ ai ≤ 109.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1 2 5 6
2

0.025s 0.006s 15