← 返回题目列表

Codeforces · 1419/A

A. 数字游戏

中文机器翻译题面 查看原题

每个人都知道《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.