Steve loves playing with palindromes. He has a string, , consisting of lowercase English alphabetic characters (i.e., a
through z
). He wants to calculate the number of ways to insert exactly lowercase character into string such that the length of the longest palindromic subsequence of increases by at least . Two ways are considered to be different if either of the following conditions are satisfied:
- The positions of insertion are different.
- The inserted characters are different.
This means there are at most different ways to insert exactly character into a string of length .
Given queries consisting of , , and , print the number of different ways of inserting exactly new lowercase letter into string such that the length of the longest palindromic subsequence of increases by at least .
Input Format
The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query over two lines:
- The first line of a query contains two space-separated integers denoting the respective values of and .
- The second line contains a single string denoting .
Constraints
- It is guaranteed that consists of lowercase English alphabetic letters (i.e.,
a
toz
) only.
Subtasks
- for of the maximum score.
- for of the maximum score.
Output Format
On a new line for each query, print the number of ways to insert exactly new lowercase letter into string such that the length of the longest palindromic subsequence of increases by at least .
Sample Input
3
1 1
a
3 2
aab
3 0
aba
Sample Output
2
1
104
Explanation
We perform the following queries:
The length of the longest palindromic subsequence of
a
is . There are two ways to increase this string's length by at least :- Insert an
a
at the start of string , making itaa
. - Insert an
a
at the end of string , making itaa
.
Both methods result in
aa
, which has a longest palindromic subsequence of length (which is longer than the original longest palindromic subsequence's length by ). Because there are two such ways, we print on a new line.- Insert an
The length of the longest palindromic subsequence of
aab
is . There is one way to increase the length by at least :- Insert a
b
at the start of string , making itbaab
.
We only have one possible string,
baab
, and the length of its longest palindromic subsequence is (which is longer than the original longest palindromic subsequence's length by ). Because there is one such way, we print on a new line.- Insert a