Spider Man

## 题目描述 彼得·帕克想和章鱼博士玩一个游戏。游戏是关于循环的。循环是一个顶点序列，第一个顶点与第二个顶点相连，第二个顶点与第三个顶点相连，依此类推，最后一个顶点与第一个顶点再次相连。循环可以由单个独立顶点组成。 最初有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秒大小的玩家获胜。 所以，不管怎样，第一个玩家输了。

Peter Parker wants to play a game with Dr. Octopus. The game is about cycles. Cycle is a sequence of vertices, such that first one is connected with the second, second is connected with third and so on, while the last one is connected with the first one again. Cycle may consist of a single isolated vertex. Initially there are $ k $ cycles, $ i $ -th of them consisting of exactly $ v_{i} $ vertices. Players play alternatively. Peter goes first. On each turn a player must choose a cycle with at least $ 2 $ vertices (for example, $ x $ vertices) among all available cycles and replace it by two cycles with $ p $ and $ x-p $ vertices where $ 1<=p&lt;x $ is chosen by the player. The player who cannot make a move loses the game (and his life!). Peter wants to test some configurations of initial cycle sets before he actually plays with Dr. Octopus. Initially he has an empty set. In the $ i $ -th test he adds a cycle with $ a_{i} $ vertices to the set (this is actually a multiset because it can contain two or more identical cycles). After each test, Peter wants to know that if the players begin the game with the current set of cycles, who wins? Peter is pretty good at math, but now he asks you to help.

The first line of the input contains a single integer $ n $ ( $ 1<=n<=100000 $ ) — the number of tests Peter is about to make. The second line contains $ n $ space separated integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ), $ i $ -th of them stands for the number of vertices in the cycle added before the $ i $ -th test.

Print the result of all tests in order they are performed. Print 1 if the player who moves first wins or 2 otherwise.

3
1 2 3

2
1
1

5
1 1 5 1 1

2
2
2
2
2

In the first sample test: In Peter's first test, there's only one cycle with $ 1 $ vertex. First player cannot make a move and loses. In his second test, there's one cycle with $ 1 $ vertex and one with $ 2 $ . No one can make a move on the cycle with $ 1 $ vertex. First player can replace the second cycle with two cycles of $ 1 $ vertex and second player can't make any move and loses. In his third test, cycles have $ 1 $ , $ 2 $ and $ 3 $ vertices. Like last test, no one can make a move on the first cycle. First player can replace the third cycle with one cycle with size $ 1 $ and one with size $ 2 $ . Now cycles have $ 1 $ , $ 1 $ , $ 2 $ , $ 2 $ vertices. Second player's only move is to replace a cycle of size $ 2 $ with $ 2 $ cycles of size $ 1 $ . And cycles are $ 1 $ , $ 1 $ , $ 1 $ , $ 1 $ , $ 2 $ . First player replaces the last cycle with $ 2 $ cycles with size $ 1 $ and wins. In the second sample test: Having cycles of size $ 1 $ is like not having them (because no one can make a move on them). In Peter's third test: There a cycle of size $ 5 $ (others don't matter). First player has two options: replace it with cycles of sizes $ 1 $ and $ 4 $ or $ 2 $ and $ 3 $ . - If he replaces it with cycles of sizes $ 1 $ and $ 4 $ : Only second cycle matters. Second player will replace it with $ 2 $ cycles of sizes $ 2 $ . First player's only option to replace one of them with two cycles of size $ 1 $ . Second player does the same thing with the other cycle. First player can't make any move and loses. - If he replaces it with cycles of sizes $ 2 $ and $ 3 $ : Second player will replace the cycle of size $ 3 $ with two of sizes $ 1 $ and $ 2 $ . Now only cycles with more than one vertex are two cycles of size $ 2 $ . As shown in previous case, with $ 2 $ cycles of size $ 2 $ second player wins. So, either way first player loses.