题目描述

彼得·帕克想和章鱼博士玩一个游戏。游戏是关于循环的。循环是一个顶点序列，第一个顶点与第二个顶点相连，第二个顶点与第三个顶点相连，依此类推，最后一个顶点与第一个顶点再次相连。循环可以由单个独立顶点组成。

最初有 $k$ 个循环，第 $i$ 个循环由精确的 $v_i$ 个顶点组成。玩家可以选择。彼得先走。在每一回合中，玩家必须在所有可用循环中选择一个具有至少 $2$ 个顶点（例如 $x$ 顶点）的循环，并将其替换为两个循环，其中 $1\le p<x$ 由玩家选择。无法移动的玩家将失去游戏（以及他的生命！）。

彼得想在和章鱼博士玩之前先测试一些初始周期的配置。最初他有一套空的。在第i个测试中，他将一个带有 $a_i$ 顶点的循环添加到集合中（这实际上是一个多集，因为它可以包含两个或更多相同的循环）。每次测试后，彼得都想知道，如果玩家以当前的循环开始游戏，谁会赢？

彼得数学很好，但现在他请你帮忙。

输入格式

输入的第一行包含一个整数 $n$（$1\le n\le 100000$）表示彼得将要进行的测试数量。

第二行包含 $n$ 个空格分隔的整数 $a_1$，$a_2$，$...$，$a_n$（$1\le a_i\le 10^9$），其中 $i-th$ 代表在第 $i-th$ 测试之前添加的循环中的顶点数。

输出格式

按顺序输出所有测试的结果。如果第一个移动的玩家获胜，请输出 $1$，否则输出 $2$。

3
1 2 3

2
1
1

在彼得的第一个测试中，只有一个 $1$ 顶点的循环。第一名选手不能移动而输。

在他的第二个测试中，有一个循环有 $1$ 个顶点，还有一个循环有 $2$ 个顶点。没有人能用 $1$ 个顶点在循环中移动。第一个玩家可以用两个 $1$ 顶点的循环来代替第二个循环，第二个玩家不能移动和丢失。

在他的第三个测试中，循环有 $1$、$2$ 和 $3$ 个顶点。像上次测试一样，没有人能在第一个循环中移动。第一个玩家可以用一个 $1$ 号和一个 $2$ 号的循环替换第三个循环。现在循环有 $1$，$1$，$2$，$2$ 个顶点。第二个玩家唯一的动作是用 $2$ 个 $1$ 号的循环来代替 $2$ 号的循环。循环为 $1$，$1$，$1$，$1$，$2$。第一个玩家用 $1$ 号的 $2$ 个循环替换最后一个循环并获胜。

5
1 1 5 1 1

2
2
2
2
2

拥有大小为 $1$ 的循环就像没有它们一样（因为没有人可以移动它们）。

在彼得的第三个测试中：有一个 $5$ 号的循环（其他的并不重要）。第一个玩家有两个选择：用 $1$ 号和 $4$ 号或 $2$ 号和 $3$ 号的循环替换它。

如果他用尺寸为 $1$ 和 $4$ 的循环替换它：只有第二个循环才重要。第二个玩家将用 $2$ 个 $2$ 号的循环来代替它。第一个玩家的唯一选择是用两个 $1$ 号的循环替换其中一个。第二个玩家对另一个循环做同样的事情。第一名选手不能移动，所以输了。

如果他用 $2$ 号和 $3$ 号的循环替换它：第二个玩家将用 $1$ 号和 $2$ 号的循环替换 $3$ 号的循环。现在只有一个以上顶点的循环是两个大小为 $2$ 的循环。如前一种情况所示，$2$ 圈 $2$ 秒大小的玩家获胜。

所以，不管怎样，第一个玩家输了。