Given two sets $S_1$ and $S_2$, a string $s$ of length $3n$ consisting only of the characters A, B, and C is considered "good" if and only if there exists a way to partition $s$ into $n$ subsequences of length 3, where each subsequence is either ABC, BCA, or CAB. Let $x$ be the number of ABC subsequences and $y$ be the number of BCA subsequences among these $n$ subsequences. We require $x \in S_1$ and $y \in S_2$.

Given a string $s$ of length $3n$ containing the characters A, B, C, and ?, you need to calculate the number of ways to replace all ? characters with one of A, B, or C such that the resulting string $s$ is good.

Perform all calculations modulo $2^{32}$.

Input

This problem contains multiple test cases per test file.

The first line contains two integers $T$ and $id$, representing the number of test cases and the subtask ID, respectively. It is guaranteed that $T = 60$, $id \in [0, 5]$, and $id = 0$ indicates the sample case.

For each test case: The first line contains an integer $n$. The second line contains a binary string $s_1$ of length $n+1$. If the $i$-th character of $s_1$ is '1', it means $i-1 \in S_1$; otherwise, it is not. The third line describes $S_2$ in the same format. The fourth line contains a string $s$ of length $3n$.

For the $i$-th test case, it is guaranteed that $n = i$.

Output

For each test case, output a single integer representing the answer.

You may choose whether or not to answer each test case; see the Note section for details.

Examples

Input 1

3 0
1
11
11
ABC
2
101
101
A????C
3
1111
1111
?????????

Output 1

1
5
1077

Note 1

This sample does not satisfy the $T = 60$ constraint and is provided only for understanding the problem.

Examples 2, 3

See the provided files, which satisfy the properties of subtasks 1 and 2, respectively.

Subtasks

For all data, it is guaranteed that $T = 60$. For the $i$-th test case in each test file, it is guaranteed that $n = i$.

All reasonable subtask dependencies are enabled during testing.

For each test case in each test file, if you do not intend to answer the test case, please output -1. Otherwise, output an integer representing the answer. If the format is incorrect, there is no guarantee that you will receive the corresponding points.

For each test file, you will be assigned a scoring coefficient $p \in [0, 1]$ based on your output. The score for each subtask is the minimum of the scoring coefficients of all test cases in that subtask, multiplied by the subtask's score.

First, your program must terminate normally and all answers you choose to provide must be correct; otherwise, $p = 0$.

Given this, let $d$ be the maximum $n$ for which your program provided an answer across all test cases. Then:

$$ p = \begin{cases} \frac{1}{20} d & d \leq 5 \\ \frac{1}{4} + \frac{1}{50} (d - 5) & 5 < d \leq 15 \\ \frac{9}{20} + \frac{3}{200} (d - 15) & 15 < d \leq 35 \\ \frac{3}{4} + \frac{1}{100} (d - 35) & 35 < d \leq 60 \\ \end{cases} $$

The approximate graph of $p$ versus $d$ is shown below.