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

给定一个只包含 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 点魔力，后手获得胜利。