爱丽丝和鲍勃决定玩一个新的石子游戏。在游戏开始时，他们挑选成一行的$n$（$1\leq n\leq10$）堆石子。爱丽丝和鲍勃轮流移动石子。

在游戏的每一步，玩家选择一堆石子，至少移除一颗石子，然后可以自由地将这堆石子中的石子移动到其他仍有石子的堆中。

例如：$n = 4$，且这些石子堆分别有（$3$，$1$，$4$，$2$）颗石子。如果玩家选择第一堆石子并移除一颗，那么它可以达到以下状态。

$2$ $1$ $4$ $2$

$1$ $2$ $4$ $2$（将一颗石子移动到第$2$堆）

$1$ $1$ $5$ $2$（将一颗石子移动到第$3$堆）

$1$ $1$ $4$ $3$（将一颗石子移动到第$4$堆）

$0$ $2$ $5$ $2$（将一颗石子移动到第$2$堆，另一颗移动到第$3$堆）

$0$ $2$ $4$ $3$（将一颗石子移动到第$2$堆，另一颗移动到第$4$堆）

$0$ $1$ $5$ $3$（将一颗石子移动到第$3$堆，另一颗移动到第$4$堆）

$0$ $3$ $4$ $2$（将两颗石子移动到第$2$堆）

$0$ $1$ $6$ $2$（将两颗石子移动到第$3$堆）

$0$ $1$ $4$ $4$（将两颗石子移动到第$4$堆）

总是爱丽丝先移动。假设爱丽丝和鲍勃在游戏中都全力以赴。 你需要编写一个程序来确定谁最终会赢得游戏。

输入

输入包含若干个测试用例。每个测试用例的第一行包含一个整数$n$，表示石子堆的数量。接下来的$n$个整数描述了游戏开始时每堆石子的数量，你可以假设每堆石子的数量不会超过$100$。

最后一个测试用例后面跟着一个$0$。

输出

对于每个测试用例，如果爱丽丝赢得游戏，输出$1$，否则输出$0$。

输入数据 1

3
2 1 3
2
1 1
0

输出数据 1

1
0

来源

LouTiancheng@POJ