Longest Palindromic Subsequence After K Changes

You are given a string S of length N and an integer K. You can change exactly K characters in S (each change can convert any character to any other character). Your task is to determine the maximum length of a palindromic subsequence that can be obtained after performing these K changes.

Let L be the length of the longest palindromic subsequence in the original string S. After K changes, the maximum possible length is given by:

$$\min(L + 2K,\; N)$$

Note that you cannot exceed the length of the string. Use dynamic programming to first calculate L and then adjust the result with K changes.

inputFormat

The first line of input contains an integer T, the number of test cases. Each of the following T lines describes a test case and contains three space-separated values: an integer N (the length of the string), a string S (of length N), and an integer K.

outputFormat

For each test case, output a single line containing the maximum possible length of a palindromic subsequence after exactly K changes. The result is computed as $$\min(L + 2K, N)$$, where L is the length of the longest palindromic subsequence in S.## sample

5
7 abacdfg 1
5 aacba 2
4 aaaa 1
6 abcdef 3
4 abcd 0

5
5
4
6
1