A. Reverse and Concatenatetime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputReal stupidity beats artificial intelligence every time.— Terry Pratchett, Hogfather, DiscworldYou are given a string s of length n and a number k. Let's denote by rev(s) the reversed string s (i.e. rev(s) = s_n s_{n-1} ... s_1). 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) + sHow 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, s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m, where n and m are the lengths of strings s and t respectively.InputThe first line contains one integer t (1 \le t \le 100) — number of test cases. Next 2 \cdot t lines contain t test cases:The first line of a test case contains two integers n and k (1 \le n \le 100, 0 \le k \le 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.OutputFor 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 10^9 under the given constraints.ExampleInput
4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab
Output
2
2
1
1
NoteIn 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 s: aabbaaaabbaa and baaaabbaaaab.
4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab

2 2 1 1 
['greedy', 'strings', '*800']