Casino Royale

Problem Description

In Casino Royale, one of the famous games is played on a decimal string $s_1s_2\dots s_n$, where $s_i\in$ {'$\texttt{1}$', '$\texttt{2}$'}. The two players move in turns, the first player moves first. In each move, the current player selects either the first bit or the last bit of the string, adds it to this player's score, and removes it from the string. The game ends when the string is empty. Both players want to maximize their scores, the one with the maximum score wins. Before the first move of a game, the observers can see a portion of bits in the string, then make a bet on who will win in the end. Little Q is the owner of the Casino Royale. He is interested in how to predict the result of the above game such that he can earn a lot of money by predicting. You will be given the initial string with some bits hidden. Little Q will then give you $q$ queries. In each query, you will be given two integers $A$ and $B$, denoting the final scores of the first player and the second player respectively, you need to report the number of distinct initial strings that will lead to this result if both players play optimally.

Input

The first line contains a single integer $T$ ($1 \leq T \leq 100$), the number of test cases. For each test case: The first line contains two integers $n$ and $q$ ($1\leq n\leq 50$, $1\leq q\leq (2n+1)(2n+1)$), denoting the length of the initial string and the number of queries. The second line contains a string $s$ of length $n$ ($s_i\in$ {'$\texttt{1}$', '$\texttt{2}$', '$\texttt{?}$'}), denoting the initial string that can be seen by the observers. Here '$\texttt{?}$' denotes the value of the corresponding bit is hidden. Each of the following $q$ lines contains two integers $A$ and $B$ ($0\leq A,B\leq 2n$), denoting a query.

Output

For each query, print a single line containing an integer, denoting the number of possible initial strings.

Sample Input

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

Sample Output

1
0
1
1
2
0

Source

2023“钉耙编程”中国大学生算法设计超级联赛（3）