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:

The current machine updates $$$a$$$ according to its type.
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$$$:

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$$$.
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$$$.
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$$$.
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$$$.
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$$$.

Strange Machine

Examples