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_ < _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.
## Input
The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 100 000) — 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_ ≤ 109), _i_\-th of them stands for the number of vertices in the cycle added before the _i_\-th test.
## Output
Print the result of all tests in order they are performed. Print _1_ if the player who moves first wins or _2_ otherwise.
[samples]
## Note
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.
彼得·帕克想和八爪博士玩一个关于环的游戏。_环_ 是一组顶点的序列，其中第一个顶点与第二个相连，第二个与第三个相连，依此类推，最后一个顶点又与第一个相连。环可以仅由一个孤立顶点组成。
初始时有 #cf_span[k] 个环，第 #cf_span[i] 个环恰好包含 #cf_span[vi] 个顶点。两名玩家轮流行动，彼得先手。每回合，玩家必须从所有可用的环中选择一个至少包含 #cf_span[2] 个顶点的环（例如，包含 #cf_span[x] 个顶点），并将其替换为两个环，分别包含 #cf_span[p] 和 #cf_span[x - p] 个顶点，其中 #cf_span[1 ≤ p < x] 由玩家自行选择。无法行动的玩家输掉游戏（并失去生命！）。
彼得希望在实际与八爪博士对战前，测试一些初始环的配置。最初他有一个空集合。在第 #cf_span[i] 个测试中，他向集合中添加一个包含 #cf_span[ai] 个顶点的环（这是一个多重集，因为可能包含两个或更多相同的环）。每次添加后，彼得想知道：如果两名玩家从当前的环集合开始游戏，谁会获胜？
彼得数学很好，但现在他需要你的帮助。
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 彼得将要进行的测试次数。
第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109])，第 #cf_span[i] 个数表示在第 #cf_span[i] 个测试前添加的环的顶点数。
按测试顺序输出每个测试的结果。如果先手玩家获胜，输出 _1_；否则输出 _2_。
在第一个样例中：
在彼得的第一个测试中，只有一个包含 #cf_span[1] 个顶点的环。先手玩家无法行动，失败。
在第二个测试中，有一个包含 #cf_span[1] 个顶点的环和一个包含 #cf_span[2] 个顶点的环。无法对包含 #cf_span[1] 个顶点的环进行操作。先手玩家可将第二个环拆分为两个包含 #cf_span[1] 个顶点的环，后手玩家因此无法行动而失败。
在第三个测试中，环的顶点数分别为 #cf_span[1]、#cf_span[2] 和 #cf_span[3]。与上一测试类似，无法对第一个环操作。先手玩家可将第三个环拆分为一个包含 #cf_span[1] 个顶点和一个包含 #cf_span[2] 个顶点的环。此时环的顶点数为 #cf_span[1]、#cf_span[1]、#cf_span[2]、#cf_span[2]。后手玩家唯一的操作是将一个大小为 #cf_span[2] 的环拆分为两个大小为 #cf_span[1] 的环，此时环的顶点数为 #cf_span[1]、#cf_span[1]、#cf_span[1]、#cf_span[1]、#cf_span[2]。先手玩家将最后一个大小为 #cf_span[2] 的环拆分为两个大小为 #cf_span[1] 的环，从而获胜。
在第二个样例中：
包含 #cf_span[1] 个顶点的环等同于不存在（因为无法对其操作）。
在彼得的第三个测试中：存在一个大小为 #cf_span[5] 的环（其他环无关紧要）。先手玩家有两个选择：将其拆分为大小为 #cf_span[1] 和 #cf_span[4] 的环，或拆分为大小为 #cf_span[2] 和 #cf_span[3] 的环。
因此，无论哪种选择，先手玩家都会输。
## Input
输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100 000]) —— 彼得将要进行的测试次数。
第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 109])，第 #cf_span[i] 个数表示在第 #cf_span[i] 个测试前添加的环的顶点数。
## Output
按测试顺序输出每个测试的结果。如果先手玩家获胜，输出 _1_；否则输出 _2_。
[samples]
## Note
在第一个样例中：
在彼得的第一个测试中，只有一个包含 #cf_span[1] 个顶点的环。先手玩家无法行动，失败。
在第二个测试中，有一个包含 #cf_span[1] 个顶点的环和一个包含 #cf_span[2] 个顶点的环。无法对包含 #cf_span[1] 个顶点的环进行操作。先手玩家可将第二个环拆分为两个包含 #cf_span[1] 个顶点的环，后手玩家因此无法行动而失败。
在第三个测试中，环的顶点数分别为 #cf_span[1]、#cf_span[2] 和 #cf_span[3]。与上一测试类似，无法对第一个环操作。先手玩家可将第三个环拆分为一个包含 #cf_span[1] 个顶点和一个包含 #cf_span[2] 个顶点的环。此时环的顶点数为 #cf_span[1]、#cf_span[1]、#cf_span[2]、#cf_span[2]。后手玩家唯一的操作是将一个大小为 #cf_span[2] 的环拆分为两个大小为 #cf_span[1] 的环，此时环的顶点数为 #cf_span[1]、#cf_span[1]、#cf_span[1]、#cf_span[1]、#cf_span[2]。先手玩家将最后一个大小为 #cf_span[2] 的环拆分为两个大小为 #cf_span[1] 的环，从而获胜。
在第二个样例中：
包含 #cf_span[1] 个顶点的环等同于不存在（因为无法对其操作）。
在彼得的第三个测试中：存在一个大小为 #cf_span[5] 的环（其他环无关紧要）。先手玩家有两个选择：将其拆分为大小为 #cf_span[1] 和 #cf_span[4] 的环，或拆分为大小为 #cf_span[2] 和 #cf_span[3] 的环。
若他选择拆分为大小为 #cf_span[1] 和 #cf_span[4] 的环：只有大小为 #cf_span[4] 的环有意义。后手玩家将其拆分为两个大小为 #cf_span[2] 的环。先手玩家只能将其中一个大小为 #cf_span[2] 的环拆分为两个大小为 #cf_span[1] 的环，后手玩家对另一个大小为 #cf_span[2] 的环做同样的操作，此时先手玩家无法行动而失败。
若他选择拆分为大小为 #cf_span[2] 和 #cf_span[3] 的环：后手玩家将大小为 #cf_span[3] 的环拆分为大小为 #cf_span[1] 和 #cf_span[2] 的环。此时仅剩两个大小为 #cf_span[2] 的环。如前例所示，面对两个大小为 #cf_span[2] 的环，后手玩家获胜。因此，无论哪种选择，先手玩家都会输。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of tests.
Let $ A = (a_1, a_2, \dots, a_n) $ be the sequence of cycle sizes added in each test, where $ a_i \in \mathbb{Z}^+ $, $ 1 \le a_i \le 10^9 $.
Let $ S_k = \{ a_1, a_2, \dots, a_k \} $ be the multiset of cycles after the $ k $-th test.
A cycle of size $ x $ is *movable* if $ x \ge 2 $.
A move consists of replacing a cycle of size $ x \ge 2 $ with two cycles of sizes $ p $ and $ x - p $, where $ 1 \le p < x $.
Define the **Grundy number** (nimber) $ g(x) $ for a cycle of size $ x $:
- $ g(1) = 0 $
- For $ x \ge 2 $:
$$
g(x) = \mathrm{mex} \left( \{ g(p) \oplus g(x - p) \mid 1 \le p < x \} \right)
$$
where $ \oplus $ denotes XOR.
**Constraints**
1. $ 1 \le n \le 100{,}000 $
2. $ 1 \le a_i \le 10^9 $ for all $ i $
**Objective**
For each $ k \in \{1, \dots, n\} $, compute the XOR-sum of Grundy numbers of all cycles in $ S_k $:
$$
G_k = \bigoplus_{i=1}^k g(a_i)
$$
If $ G_k \ne 0 $, output $ 1 $ (first player wins); otherwise, output $ 2 $ (second player wins).
**Note**: It can be shown that $ g(x) = x - 1 $ for all $ x \ge 1 $.