I. Rayo hates unique substrings (Neon)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Rayo loves strings, but he dislikes unique substrings. Kilani decided to give him a challenge involving both.

You are given a string $$$s$$$ of length $$$n$$$ and an integer $$$m$$$.

Construct a new string $$$t$$$ of length $$$m$$$ as follows:

For each index $$$i$$$ ($$$1 \le i \le m$$$):

$$$$$$ t[i] = \begin{cases} s[i], & \text{if } i \le n, \\ s[i - n], & \text{otherwise}. \end{cases} $$$$$$

In other words, after copying the first $$$n$$$ characters from $$$s$$$, the string continues by repeating the same pattern every $$$n$$$ characters.

Your task is to determine the number of distinct (unique) substrings of the string $$$t$$$.

Input

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

For each test case:

  • The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n \le m \le 10^9)$$$ — the length of the string $$$s$$$ and the required length of $$$t$$$.
  • The second line contains a string $$$s$$$ of length $$$n$$$ that contains lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^2$$$.

Output

For each test case, print a single integer — the number of distinct substrings of the constructed string $$$t$$$.

Example
Input
2
2 3
ah
3 5
aaa
Output
5
5
Note

In the first sample case, the constructed string is aha.

It has 5 distinct sub strings which are: [a, ah, aha, ha, h].

In the second sample case, the constructed string is aaaaa.

It has 5 distinct sub strings which are: [a, aa, aaa, aaaa, aaaaa].