在 Casino Royale 中，一个著名的游戏是在一个十进制字符串 $s_1s_2 \dots s_n$ 上进行的，其中 $s_i \in \{'1', '2'\}$。两名玩家轮流行动，先手玩家先行。在每一轮中，当前玩家选择字符串的首位或末位，将其加到自己的得分中，并将其从字符串中移除。当字符串为空时游戏结束。两名玩家都希望最大化自己的得分，得分最高者获胜。

在游戏开始前，观察者可以看到字符串中部分位的值，然后对最终谁会获胜进行下注。Little Q 是 Casino Royale 的老板。他想知道如何预测上述游戏的结果，以便通过预测赚取大量金钱。

你将获得一个包含部分隐藏位的初始字符串。随后 Little Q 会给你 $q$ 次询问。在每次询问中，你会得到两个整数 $A$ 和 $B$，分别表示先手玩家和后手玩家的最终得分。你需要报告在双方均采取最优策略的情况下，导致该结果的初始字符串的可能数量。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 50, 1 \le q \le (2n + 1)(2n + 1)$)，分别表示初始字符串的长度和询问次数。

第二行包含一个长度为 $n$ 的字符串 $s$ ($s_i \in \{'1', '2', '?'\}$)，表示观察者可见的初始字符串。其中 '?' 表示对应位的值是隐藏的。

接下来的 $q$ 行，每行包含两个整数 $A$ 和 $B$ ($0 \le A, B \le 2n$)，表示一次询问。

输出格式

对于每次询问，输出一行，包含一个整数，表示可能的初始字符串数量。

样例

输入 1

2
3 2
121
2 2
1 3
2 4
??
1 1
2 2
2 1
1 2

输出 1

1
0
1
1
2
0