Restoration of the row

In many practical applications, such as web search or genome decoding, certain string operations are essential. For instance, reconstructing a string from given data is often required.

You are provided with two strings, (S_1) and (S_2). It is known that one of these strings is a suffix of the target string (S), while the other is a prefix. The length of the target string (L) is also given, along with the information that (S) consists solely of lowercase Latin letters.

Your task is to determine how many strings meet these criteria. Given that this number can be very large, you need to output it modulo (m).

Input

The first line contains a single integer (t) ((1 $\le$ t $\le$ 100)) — the number of test cases.

Each test case consists of three lines. The first line contains two integers: (L) and (m) ((1 $\le$ L $\le$ 10^9), (1 $\le$ m $\le$ 10^4)). The second and third lines contain the strings (S_1) and (S_2), respectively. These strings are non-empty, composed of lowercase Latin letters, and have lengths not exceeding 200 characters.

Output

For each test case, output the remainder when the number of strings satisfying the conditions is divided by (m), on a separate line.

Examples