Let's consider the alphabet consisting of the first c roman uppercase letters, i.e. {A, B, C, D, E, F} if c is 6.

We will call two words quite different, if there is no common subsequence of length more than one between those two words. For example ABC and CBA are quite different, but ABBA and CADDCAD aren't, because AA is a subsequence of both words.

Given a word w you are to find the number of words of length n that are quite different from w.

Input

The first line will contain the number of test cases (at most 20). Then there will be pairs of lines, the first one containing the numbers n (n will fit into a 32-bit signed integer and will be non-negative) and c (1 <= c <= 6), the second one the word w. w will only consist of the first c letters of the roman alphabet and will have at most 10000 characters.

Output

Print one line for each test case, consisting only of the number of words that are quite different from w. As this number can be quite large, you just have to output its remainder when dividing by 4242.

Example

Input:
3
3 3
ABC
4 4
CADDCAD
100 3
A

Output:
10
13
2223