最开始由k个循环，第i个循环有vi个顶点。玩家交替着玩。彼得先手。在每轮玩家必须从所有可选循环中选择一个至少有两个顶点的循环（比如，x个顶点）并将它用含有p和x-p个顶点的两个循环替代(1<= p < x)。当这个玩家不可以进行操作时他就输了。
彼得想在和章鱼博士正式游戏前测试一些初始循环集合的结构。开始他有一个空集合。在第i个测试中他添加一个含有ai个顶点的循环到集合中（这实际上是一个多重集合，因为它可以包含多个相同循环）。在每次测试后，彼得想知道在当前循环集下，谁能赢？
彼得很擅长数学，但是现在他向你寻求帮助。
第一行输入包含一个整数n(1 <= n <= 100000)，代表彼得将进行试验的次数
第二行包含n个用空格分隔的整数a1,a2,……,an(1<=ai<=10^9)，第i个数代表在第i次测试前加入循环的顶点数
按试验先后输出试验结果。如果先手赢打印1，否则打印2.
输入样例
3
1 2 3
输出样例
2
1
1
输入样例
5
1 1 5 1 1
输出样例
2
2
2
2
2
在第一个样例中：
彼得的第一次试验，只有一个循环，它有一个顶点，玩家无法做任何操作，输。
第二次试验，有一个含一个顶点的循环和一个含有两个顶点。Merit可以移动含一个顶点的循环。第一个玩家可以用两个1顶点循环来代替第二个缓缓，第二个玩家无法操作失败。
第三次试验，循环有1，2，3个顶点。就像上一次试验。没人可以对第一个循环操作。第一个玩家可以用一个循环一和一个循环二来替换循环三。现在循环有1，1，2，2个顶点。第二个玩家只能用两个循环一来替换循环二。第一个玩家可以用两个循环一来替换循环二。玩家一赢。
在第二个样例中：
存在含一个顶点的循环相当于不存在（因为没人可以移动它们）
在彼得的第三次试验中：有一个含五个顶点的循环（其它的不影响）。第一个玩家有两种选择：用含一个顶点和四个顶点的循环或含两个顶点和三个顶点的循环替换它。
3
1 2 32
1
1