题目描述

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

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

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

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

输入格式

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

第二行包含n个空格分隔的整数a1，a2，…，an （1<=ai<=10^9），其中i-th代表在第i-th测试之前添加的循环中的顶点数。

输出格式

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

说明/提示

在第一个样例中：

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

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

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

在第二个样例中：

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

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

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

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

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

样例

3
1 2 3

2
1
1

5
1 1 5 1 1

2
2
2
2
2