在果冻的指示下，贤者禾枫创造了大量魔法人偶辅助魔法师工作。为了训练魔法人偶的思考能力，她打算让人偶两两之间进行一种游戏，具体规则如下：

给定一个只包含 0 和 1 的字符串 $s$ ，其长度为 $n$ ，两个人偶轮流在以下两种操作中选择一种执行：

1. 将字符串反转，即从后往前重新书写字符串。如 00001 反转后变为 10000 。这个操作不耗费魔力。
2. 将字符串中的 $1$ 个 0 改为 1 。耗费 $1$ 点魔力。

当字符串中的每个字符都变为 1 时游戏结束。此时，耗费魔力更少的那个人偶获得胜利。若两个人偶所耗费的魔力相同，则游戏平局。

为了让游戏更加有趣，禾枫添加了一个限制：

操作 $1$ 只能在当前字符串不是回文串，且前一次操作不是操作 $1$ 时执行。

其中，回文串是指从后往前读和从前往后读都相同的字符串，即：记下标从 $1$ 开始，长为 $n$ 的回文串 $s$ 满足对任意 $i$ ( $1\le i \le n$ )， $s[i]=s[n-i+1]$ 。

在先手的第一次操作的情况下，不存在“前一次操作”，此时只需要满足字符串不是回文串的条件即可执行操作 $1$ 。

举个例子，当第一个人偶执行了操作 $1$ 后，即使此时的字符串不是回文串，按照限制，第二个人偶仍然无法执行操作 $1$ 。反之亦然。

现在已知一个字符串，并且两个人偶都会以最优策略进行游戏，禾枫想要知道游戏的结果。

输入一个整数 $T$ ( $1 \le T \le 10^3$ )，代表接下来有 $T$ 个测试用例。

对于每个测试用例：

输入一行一个整数 $n$ 。

接下来一行输入一个长度为 $n$ ，并且只包含 0 和 1 的字符串。

对于 $20\%$ 分数的数据，$1\le n\le5$ ， $\sum n \le 10$ 且保证输入的字符串是回文串。

对于 $60\%$ 分数的数据，$1\le n\le10^3$ ，$\sum n \le 10^3$ 且保证输入的字符串是回文串。

对于 $100\%$ 分数的数据， $1\le n\le10^3$ ，$\sum n \le 10^5$ 且保证输入的字符串中至少有 $1$ 个 0

对于每个测试用例，第一行输出一个整数。若先手胜利，输出 $1$ ；若后手胜利，输出 $-1$ ；若游戏平局，输出 $0$

对于样例 $1$ 中的测试用例 $1$ :

字符串已经是回文串，先手只能执行操作 $2$ ，之后字符串变为 1 ，游戏结束。

此时先手耗费 $1$ 点魔力，后手耗费 $0$ 点魔力，后手获得胜利。

对于样例 $1$ 中的测试用例 $2$ :

字符串已经是回文串，先手只能执行操作 $2$ ，然后后手会执行操作 $1$ ，由于限制的存在，先手只能继续执行操作 $2$ ，游戏结束。

此时先手耗费 $2$ 点魔力，后手耗费 $0$ 点魔力，后手获得胜利。