You are given $n$ machines arranged in a circle, where $n$ is at most $20$. Each machine is either of type A or type B. The machines are numbered clockwise from $1$ to $n$, and the type of the $i$-th machine is denoted by $s_i$. Each machine takes an integer $x$ and updates it according to its type:

• Type A: Decrease $x$ by $1$. Formally, update $x := x - 1$.
• Type B: Replace $x$ with the floor of half its value. Formally, update $x := \left\lfloor\frac{x}{2}\right\rfloor$, where $\lfloor y\rfloor$ denotes the floor of $y$, which is the greatest integer less than or equal to $y$.

You are given $q$ queries, each consisting of a single integer $a$. In each query, you start at machine $1$ holding an integer $a$. Each second, the following two actions occur in order:

1. The current machine updates $a$ according to its type.
2. Then, move one step clockwise to the next machine. Formally
   • If you are at machine $i$ where $1 \le i \le n - 1$, move to machine $i + 1$.
   • If you are at machine $n$, move to machine $1$.

This process continues until your integer $a$ becomes $0$. For each query, determine the number of seconds required for $a$ to reach $0$.

Note that all queries are independent of each other.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1\le n\le 20$, $1\le q\le 10^4$) — the number of machines, and the number of queries, respectively.

The second line of each test case contains a string $s$ ($|s| = n$ and $s_i = \mathtt{A} \text{ or }\mathtt{B}$) — the types of the machines.

The third line of each test case contains $q$ integers $a_1, a_2, \ldots, a_q$ ($1\le a_i\le 10^9$) — the initial integer of each query.

Note that there are no constraints on the sum of $n$ over all test cases.

It is guaranteed that the sum of $q$ over all test cases does not exceed $10^4$.

Output

For each test case, output $q$ integers representing the answers to each query.

Note

In the first test case, the queries are as follows:

• Query $1$: $a = 3$
  1. Start at machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{3}{2}\right\rfloor = 1$.
  2. Move to machine $2$. Machine $2$ decreases $a$ by $1$. Now, $a = 1 - 1 = 0$.Therefore, it takes $2$ seconds for $a$ to reach $0$.
• Query $2$: $a = 4$
  1. Start at machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{4}{2}\right\rfloor = 2$.
  2. Move to machine $2$. Machine $2$ decreases $a$ by $1$. Now, $a = 2 - 1 = 1$.
  3. Move back to machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{1}{2}\right\rfloor = 0$.Therefore, it takes $3$ seconds for $a$ to reach $0$.

In the second test case, there is only one query with $a = 20$:

1. Start at machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{20}{2}\right\rfloor = 10$.
2. Move to machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{10}{2}\right\rfloor = 5$.
3. Move to machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{5}{2}\right\rfloor = 2$.
4. Move to machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{2}{2}\right\rfloor = 1$.
5. Move to machine $1$. Machine $1$ replaces $a$ with the floor of half its value. Now, $a = \left\lfloor\frac{1}{2}\right\rfloor = 0$.

Therefore, it takes $5$ seconds for $a$ to reach $0$.

Samples

3
2 2
BA
3 4
1 1
B
20
6 4
BAABBA
2 8 32 95

2
3
5
2
5
8
11