Classical Hard Game Problem

$\mathbb{Mr. \ COACH \ 1}$ and $\mathbb{Mr. \ COACH \ 2}$ are playing a game.

They start from a set of $n$ distinct positive integers. The coaches take turns. In one move a coach chooses two distinct integers $a$ and $b$ from the set such that the set does not contain
|$a - b$| and then add |$a - b$| to the set. If one of the coaches cannot make any valid move he loses.

You need to find which coach will win. $\mathbb{Mr. \ COACH \ 1}$ makes the first move.

Input

The first line contains a single integer $n$ ($2 \le n \le 10^3$) – the length of the initial set $s$.
The second line contains $n$ distinct positive integers $s_1, s_2, \ldots, s_n$ ($0 < s_i \le 10^9$).

Output

Print 1 if $\mathbb{Mr. \ COACH \ 1}$ wins or 2 if $\mathbb{Mr. \ COACH \ 2}$ wins.

Example 1

stdin

2
3 2

stdout

1

Example 2

stdin

2
3 5

stdout

1

Example 3

stdin

3
7 5 6

stdout

2