Двоє грають в гру. Є кілька купок сірників. За один зхід дозволяється взяти будь-яку ненульову кількість сірників з будь-якої купки. Хто не може зробити хід, той програв. Визначіть, хто виграє при правильній грі.

Формат вхідних даних

В першому рядку число N - кількість купок.
В другому рядку N цілих чисел - кількість сірників в кожній купці. Всі числа не більші за 100000.

Формат вихідних даних

Виведіть 1, якщо виграє перший гравець або 2, якщо виграє другий гравець.

Приклад вхідних даних-1

1
10

Приклад вихідних даних-1

1

Приклад вхідних даних-2

2
1 1

Приклад вихідних даних-2

2