每个人都知道《Valorant》中的特工决定谁将扮演攻击者,谁将扮演防御者。为了做到这一点,Raze 和 Breach 决定玩一场数字游戏的 $$$t$$$ 比赛......
在数字游戏的每场$$$t$$$比赛中,都会生成一个正整数。它由 $$$n$$$ 数字组成。该整数的位数从最高位到最低位从 $$$1$$$ 到 $$$n$$$ 进行编号。宣布该整数后,比赛开始。
特工轮流进行游戏。拉兹开始。在一轮中,代理可以选择任何未标记的数字并对其进行标记。 Raze 可以选择奇数位置的数字,但不能选择偶数位置的数字。违规者可以选择偶数位置的数字,但不能选择奇数位置的数字。当只剩下一位未标记的数字时,比赛结束。如果最后一位数字是奇数,则 Raze 获胜,否则 Breach 获胜。
可以证明,在比赛结束之前(对于每个具有 $$$n$$$ 数字的初始整数),每个智能体都有能力进行转弯,即至少有一个未标记的数字站在所需奇偶性的位置上。
对于每场 $$$t$$$ 比赛,找出哪位代理人获胜,如果他们都想获胜并发挥最佳状态。
输入
输入的第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 100)$$$ — 匹配数。
每个比赛描述的第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 10^3)$$$ — 生成号码的位数。
每个比赛描述的第二行包含一个 $$$n$$$ 位正整数,不带前导零。
输出
对于每场比赛,如果 Raze 获胜,则打印 $$$1$$$;如果 Breach 获胜,则打印 $$$2$$$。
示例
输入 #1
4 1 2 1 3 3 102 4 2069
输出 #1
2 1 1 2
注意
第一场比赛无人能转,剩下的数字是$$$2$$$,是偶数,所以Breach获胜。
第二场比赛剩下的唯一数字是 $$$3$$$,很奇怪,所以 Raze 获胜。
在第三场比赛中 Raze 可以标记最后一位数字,之后 Breach 只能标记 $$$0$$$。 $$$1$$$ 将是剩下的最后一位数字,这很奇怪,所以 Raze 获胜。
第四场比赛无论Raze怎么打,Breach都能标记$$$9$$$,最后会出现数字$$$0$$$。 It's even, so Breach wins.