题目描述

众所周知，在 Valorant 中，特工们需要决定谁将作为进攻方，谁将作为防守方。为此，Raze 和 Breach 决定进行 $t$ 场数字游戏的对决……

在每一场数字游戏中，会生成一个正整数。该整数由 $n$ 位数字组成。数字从高位到低位依次编号为 $1$ 到 $n$。在这个整数公布后，比赛开始。

两位特工轮流行动。Raze 先手。在每一回合中，特工可以选择任意一个未被标记的数字并将其标记。Raze 只能选择奇数位置上的数字，不能选择偶数位置上的数字。Breach 只能选择偶数位置上的数字，不能选择奇数位置上的数字。当只剩下最后一个未被标记的数字时，比赛结束。如果最后剩下的数字是奇数，则 Raze 获胜，否则 Breach 获胜。

可以证明，在比赛结束前（对于任意初始的 $n$ 位整数），每位特工在自己的回合都至少有一个可选的未被标记的数字。

对于每一场比赛，若两位特工都采取最优策略，请你判断最终哪位特工会获胜。

输入格式

输入的第一行包含一个整数 $t$ $(1 \le t \le 100)$，表示比赛场数。

每场比赛的第一行包含一个整数 $n$ $(1 \le n \le 10^3)$，表示生成的数字的位数。

每场比赛的第二行包含一个没有前导零的 $n$ 位正整数。

输出格式

对于每一场比赛，若 Raze 获胜则输出 $1$，若 Breach 获胜则输出 $2$。

说明/提示

在第一场比赛中，没有人可以行动，最后剩下的数字是 $2$，它是偶数，因此 Breach 获胜。

在第二场比赛中，最后剩下的数字是 $3$，它是奇数，因此 Raze 获胜。

在第三场比赛中，Raze 可以标记最后一位数字，之后 Breach 只能标记 $0$，最后剩下 $1$，它是奇数，因此 Raze 获胜。

在第四场比赛中，无论 Raze 如何操作，Breach 都可以标记 $9$，最后剩下的数字是 $0$，它是偶数，因此 Breach 获胜。

由 ChatGPT 4.1 翻译

样例

4
1
2
1
3
3
102
4
2069

2
1
1
2