Two people are playing a game. There are several piles of matches. In one move, it is allowed to take any non-zero number of matches from any pile, whoever cannot make a move loses. Determine who wins when played correctly.
Input
The first line of the input file contains a natural number N — number of heaps. The second line contains N integers — the number of matches in piles. All numbers in the input file do not exceed 100000.
Output
Print "1" if the first player wins or "2" if the second player wins.
|
Enter |
Output |
1
10 |
1 |
2
1 1
|
2 |