Longest Palindromic Substring After Modifications

Given a string \(S\) and an integer \(k\), you are allowed to change at most \(k\) characters in any substring to obtain a palindrome. More formally, for a substring \(S[i \ldots j]\), let \(m\) be the number of indices \(t\) (with \(0 \le t \le \lfloor (j-i)/2 \rfloor\)) such that \(S[i+t] \neq S[j-t]\). The substring can be converted into a palindrome if \(m \le k\). Your task is to determine the length of the longest substring which can be made into a palindrome by performing at most \(k\) modifications.

Note: A modification consists of changing a single character to any other character.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains a test case, with an integer \(k\) and a string \(S\) separated by a space.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest palindromic substring that can be obtained after making at most \(k\) modifications.

5
2 abca
1 abcdef
0 racecar
0 abc
5 abcdefedcba

4
3
7
1
11