We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Longest Palindromic Subsequence

Longest Palindromic Subsequence

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:

  1. The first line of a query contains two space-separated integers denoting the respective values of and .
  2. The second line contains a single string denoting .

Constraints

  • It is guaranteed that consists of lowercase English alphabetic letters (i.e., a to z) 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:

  1. The length of the longest palindromic subsequence of a is . There are two ways to increase this string's length by at least :

    1. Insert an a at the start of string , making it aa.
    2. Insert an a at the end of string , making it aa.

    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.

  2. The length of the longest palindromic subsequence of aab is . There is one way to increase the length by at least :

    1. Insert a b at the start of string , making it baab.

    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.