在果冻的指示下，贤者禾枫创造了大量魔法人偶辅助魔法师工作。为了训练魔法人偶的思考能力，她打算让人偶两两之间进行一种游戏，具体规则如下：
给定一个只包含 0 和 1 的字符串 s ，其长度为 n ，两个人偶轮流在以下两种操作中选择一种执行：
00001 反转后变为 10000 。这个操作不耗费魔力。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
样例
| 标准输入 复制文本 |
2 1 0 2 00 |
| 标准输出 复制文本 |
-1 -1 |
提示
对于样例 1 中的测试用例 1 :
字符串已经是回文串，先手只能执行操作 2 ，之后字符串变为 1 ，游戏结束。
此时先手耗费 1 点魔力，后手耗费 0 点魔力，后手获得胜利。
对于样例 1 中的测试用例 2 :
字符串已经是回文串，先手只能执行操作 2 ，然后后手会执行操作 1 ，由于限制的存在，先手只能继续执行操作 2 ，游戏结束。
此时先手耗费 2 点魔力，后手耗费 0 点魔力，后手获得胜利。