彼得·帕克想和章鱼博士玩一个游戏。游戏是关于循环的。循环是一系列顶点,第一个顶点与第二个顶点相连,第二个顶点与第三个顶点相连,依此类推,最后一个顶点又与第一个顶点相连。循环可以由单个孤立的顶点组成。
最初有 k 个循环,其中第 i 个循环由 vi 个顶点组成。玩家交替进行游戏。彼得先走。每回合,玩家必须在所有可用循环中选择一个至少有 2 个顶点(例如 x 顶点)的循环,并将其替换为两个具有 p 和 x - p 顶点的循环,其中 1 ≤ p < x 由玩家选择。无法采取行动的玩家将输掉游戏(以及他的生命!)。
彼得想在实际与章鱼博士一起玩之前测试初始循环组的一些配置。最初他有一个空集。在第 i 个测试中,他向集合中添加了一个具有 ai 个顶点的循环(这实际上是一个多重集,因为它可以包含两个或多个相同的循环)。每次测试后,Peter 想知道如果玩家以当前的一组循环开始游戏,谁会获胜?
彼得的数学非常好,但现在他请你帮忙。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) - Peter 即将进行的测试数量。
第二行包含n个空格分隔的整数a1, a2, ..., an (1 ≤ ai ≤ 109),其中第i个表示第i次测试之前添加的循环中的顶点数。
输出
按执行顺序打印所有测试的结果。如果先移动的玩家获胜则打印 1,否则打印 2。
示例
输入 #1
3 1 2 3
输出 #1
2 1 1
输入 #2
5 1 1 5 1 1
输出 #2
2 2 2 2 2
注意
在第一个样本测试中:
在 Peter 的第一个测试中,只有一个循环有 1 个顶点。第一个玩家无法移动并失败。
在他的第二次测试中,有一个具有 1 个顶点的循环,一个具有 2 个顶点的循环。没有人可以在具有 1 个顶点的循环上进行移动。第一个玩家可以用两个 1 个顶点的循环替换第二个循环,第二个玩家不能进行任何移动并失败。
在他的第三次测试中,循环有 1、2 和 3 个顶点。和上次测试一样,第一轮没人能采取行动。第一个玩家可以用一个尺寸为 1 的循环和一个尺寸为 2 的循环替换第三个循环。现在循环有 1, 1, 2, 2 个顶点。第二个玩家唯一的举动是用 2 个尺寸为 1 的周期替换一个尺寸为 2 的周期。周期为 1, 1, 1, 1, 2。第一个玩家用 2 个尺寸为 1 的周期替换最后一个周期并获胜。
在第二个样本测试中:
拥有大小为 1 的循环就像没有它们一样(因为没有人可以对它们采取行动)。
在Peter的第三次测试中:有一个大小为5的循环(其他不重要)。第一个玩家有两个选择:将其替换为尺寸为 1 和 4 或 2 和 3 的循环。
- 如果他用尺寸 1 和 4 的周期替换它:只有第二个周期重要。第二个玩家将用 2 个尺寸为 2 的周期替换它。第一个玩家唯一的选择是用两个尺寸为 1 的周期替换其中一个。第二个玩家对另一个周期做同样的事情。第一个玩家无法采取任何行动并失败。
- 如果他将其替换为尺寸为 2 和 3 的循环:第二个玩家将用两个尺寸为 1 和 2 的循环替换尺寸为 3 的循环。现在只有具有多个顶点的循环才是两个尺寸为 2 的循环。如前一情况所示,拥有 2 个尺寸为 2 的循环第二个玩家获胜。
所以,无论哪种方式,第一个玩家都会失败。