Distinct Reversed Strings

Given a string s of length n and an integer k, you are required to determine the number of distinct strings that can be obtained by applying exactly k reversal operations on the string. In one operation, you may select any contiguous substring of s and reverse it.

The answer can be determined by the following rules:

• If \( k = 0 \), the string remains unchanged, so the answer is \( 1 \).
• If \( k = 1 \), it turns out that exactly n distinct strings can be produced.
• If \( k \ge 2 \), the number of distinct strings is \( 2^{n-1} \).

For example:

• For s = "abc" with n = 3 and k = 1, the answer is 3.
• For s = "abcd" with n = 4 and k = 2, the answer is 8 (since \(2^{4-1} = 8\)).
• For s = "abcde" with n = 5 and k = 0, the answer is 1.

You are given multiple test cases; process each one according to the described rules.

inputFormat

The first line contains an integer T, the number of test cases.

Each of the next T lines contains two integers n and k followed by the string s, separated by spaces.

outputFormat

For each test case, output a single line with the number of distinct strings that can be formed after exactly k reversal operations.

## sample

3
3 1 abc
4 2 abcd
5 0 abcde

3
8
1

</p>