E. E
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Let $$$s$$$ be a string consisting of characters 'A', 'B' or 'C'. A regular partition of $$$s$$$ is a partition of $$$s$$$ in subsequences such that every subsequence is equal to one of the following:

  • "AB",
  • "AC",
  • "BC".

A string $$$s$$$ is a regular ternary string if it has a regular partition.

Given an integer $$$n$$$ and a string $$$p$$$, count the number of regular ternary strings of size $$$n$$$ that has $$$P$$$ as its prefix. Since the number can be really big, output it modulo $$$998'244'353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 200$$$) — the number of testcases.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1 \leq m \leq n \leq 200$$$) — the size of the strings we want to count and the size of the prefix, respectively.

The second line contains a string $$$p$$$ ($$$1 \leq |p| \leq n$$$; $$$p_i \in \{'A', 'B', 'C'\}$$$) — the prefix of the strings.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$200$$$.

Output

Output a single integer — the number of regular ternary strings of size $$$n$$$ that has $$$p$$$ as its prefix, modulo $$$998'244'353$$$.

Example
Input
6
4 1
A
4 4
ABAC
4 4
BCBC
4 4
CACB
6 1
A
123 3
ABC
Output
12
1
1
0
90
0
Note

For the first case with $$$n = 4$$$ and $$$p$$$ = A, the following strings are regular and has $$$p$$$ as its prefix:

  • AABB,
  • AABC,
  • AACB,
  • AACC,
  • ABAB,
  • ABAC,
  • ABBC,
  • ABCB,
  • ABCC,
  • ACAB,
  • ACAC,
  • ACBC.