- Prepare
- Algorithms
- Dynamic Programming
- Longest Palindromic Subsequence

# 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:

- 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`

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:

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 it`aa`

. - 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.- 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 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.- Insert a