CF1419A.Digit Game

Everyone knows that agents in Valorant decide, who will play as attackers, and who will play as defenders. To do that Raze and Breach decided to play $t$ matches of a digit game...

In each of $t$ matches of the digit game, a positive integer is generated. It consists of $n$ digits. The digits of this integer are numerated from $1$ to $n$ from the highest-order digit to the lowest-order digit. After this integer is announced, the match starts.

Agents play in turns. Raze starts. In one turn an agent can choose any unmarked digit and mark it. Raze can choose digits on odd positions, but can not choose digits on even positions. Breach can choose digits on even positions, but can not choose digits on odd positions. The match ends, when there is only one unmarked digit left. If the single last digit is odd, then Raze wins, else Breach wins.

It can be proved, that before the end of the match (for every initial integer with $n$ digits) each agent has an ability to make a turn, i.e. there is at least one unmarked digit, that stands on a position of required parity.

For each of $t$ matches find out, which agent wins, if both of them want to win and play optimally.

众所周知，《Valorant》中的特工需要决定谁担任进攻方，谁担任防守方。为此，Raze 和 Breach 决定进行 $t$ 局数字游戏……

在数字游戏的 $t$ 局对局中，每局都会生成一个正整数，该整数由 $n$ 位数字组成。这些数字从高位到低位依次编号为 $1$ 至 $n$。该整数公布后，对局开始。

特工们轮流行动，Raze 先手。在一轮行动中，一名特工可任选一个尚未被标记的数字并将其标记。Raze 只能选择位于奇数位置（即位置编号为奇数）上的数字，而不能选择偶数位置上的数字；Breach 则只能选择位于偶数位置上的数字，而不能选择奇数位置上的数字。当仅剩一个未被标记的数字时，对局结束。若这唯一剩下的数字是奇数，则 Raze 获胜；否则 Breach 获胜。

可以证明：在对局结束前（即对于任意一个初始的 $n$ 位整数），双方特工始终都有合法的行动可执行——即总存在至少一个未被标记的、且位于所需奇偶性位置上的数字。

对于 $t$ 局对局中的每一局，请判断：若双方均采取最优策略且都想获胜，最终哪位特工获胜？

First line of input contains an integer $t$ $(1 \le t \le 100)$ — the number of matches.

The first line of each match description contains an integer $n$ $(1 \le n \le 10^3)$ — the number of digits of the generated number.

The second line of each match description contains an $n$-digit positive integer without leading zeros.

输入的第一行包含一个整数 $t$（$1 \le t \le 100$）—— 表示比赛的场数。

每场比赛描述的第一行包含一个整数 $n$（$1 \le n \le 10^3$）—— 表示生成数字的位数。

每场比赛描述的第二行包含一个 $n$ 位正整数，且不含前导零。

For each match print $1$, if Raze wins, and $2$, if Breach wins.

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

In the first match no one can make a turn, the only digit left is $2$, it's even, so Breach wins.

In the second match the only digit left is $3$, it's odd, so Raze wins.

In the third match Raze can mark the last digit, after that Breach can only mark $0$. $1$ will be the last digit left, it's odd, so Raze wins.

In the fourth match no matter how Raze plays, Breach can mark $9$, and in the end there will be digit $0$. It's even, so Breach wins.

第一局比赛中，无人能进行操作，唯一剩余的数字是 $2$，它是偶数，因此 Breach 获胜。

第二局比赛中，唯一剩余的数字是 $3$，它是奇数，因此 Raze 获胜。

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

第四局比赛中，无论 Raze 如何操作，Breach 均可标记 $9$，最终剩余的数字为 $0$。它是偶数，因此 Breach 获胜。