# Reverse and Concatenate codeforces solution – How many different strings can you get as a result of performing exactly 𝑘k operations (possibly of different kinds) on the original string 𝑠s?

You are given a string 𝑠s of length 𝑛n and a number 𝑘k. Let’s denote by 𝑟𝑒𝑣(𝑠)rev(s) the reversed string 𝑠s (i.e. 𝑟𝑒𝑣(𝑠)=𝑠𝑛𝑠𝑛1...𝑠1rev(s)=snsn−1…s1). You can apply one of the two kinds of operations to the string:

• replace the string 𝑠s with 𝑠+𝑟𝑒𝑣(𝑠)s+rev(s)
• replace the string 𝑠s with 𝑟𝑒𝑣(𝑠)+𝑠rev(s)+s

How many different strings can you get as a result of performing exactly 𝑘k operations (possibly of different kinds) on the original string 𝑠s?

In this statement we denoted the concatenation of strings 𝑠s and 𝑡t as 𝑠+𝑡s+t. In other words, 𝑠+𝑡=𝑠1𝑠2...𝑠𝑛𝑡1𝑡2...𝑡𝑚s+t=s1s2…snt1t2…tm, where 𝑛n and 𝑚m are the lengths of strings 𝑠s and 𝑡t respectively.

Input

The first line contains one integer 𝑡t (1𝑡1001≤t≤100) — number of test cases. Next 2𝑡2⋅t lines contain 𝑡t test cases:

The first line of a test case contains two integers 𝑛n and 𝑘k (1𝑛1001≤n≤1000𝑘10000≤k≤1000) — the length of the string and the number of operations respectively.

The second string of a test case contains one string 𝑠s of length 𝑛n consisting of lowercase Latin letters.

Output

For each test case, print the answer (that is, the number of different strings that you can get after exactly 𝑘k operations) on a separate line.

It can be shown that the answer does not exceed 109109 under the given constraints.

Example
input

Copy
4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab

output

Copy
2
2
1
1

Note

In the first test case of the example:

After the first operation the string 𝑠s can become either aabbaa or baaaab. After the second operation there are 2 possibilities for 𝑠saabbaaaabbaa and baaaabbaaaab.