Longest k-Palindromic Substring

Given a string s and an integer k, a substring of s is called a k-palindrome if it can be considered a palindrome when allowing at most k mismatches when comparing characters from both ends. Formally, for a substring sub of length n, let its mismatch count be computed as

$$ \sum_{i=1}^{\lfloor n/2 \rfloor} I(sub_i \neq sub_{n-i+1}) \le k $$

Your task is to determine the length of the longest substring of s that is a k-palindrome. Use a brute-force approach to examine all possible substrings and check if they satisfy the k-palindrome property.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains an integer T, representing the number of test cases.
2. For each test case, there are two lines:
   • The first line is a string s (which may be empty).
   • The second line is an integer k.

outputFormat

For each test case, output a single integer on a new line indicating the length of the longest k-palindromic substring of s.

## sample

3
abcde
1
aab
0
abcdcba
1

3
2
7

</p>