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). 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. 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 li