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

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000, 1 ≤ a_i ≤ 10⁹.

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

№	Входной файл (input.txt)	Выходной файл (output.txt)
1	4 1 2 5 6 скопировать	2 скопировать

---