Minimum Changes to Palindrome

A palindrome is a string that reads the same forwards and backwards. Given a string s and an integer k, your task is to determine the minimum number of character changes needed to make s a palindrome if it is possible to do so with at most k changes. If it is not possible, output -1.

The number of changes needed can be calculated as:

$$changes\_needed = \sum_{i=0}^{\lfloor\frac{n}{2}\rfloor - 1}[s[i] \neq s[n-1-i]]$$

where \( n \) is the length of the string, and the indicator function \([s[i] \neq s[n-1-i]]\) is 1 if \( s[i] \) differs from \( s[n-1-i] \), and 0 otherwise.

If changes_needed ≤ k, output changes_needed; otherwise, output -1.

inputFormat

The first line contains a single integer T, the number of test cases. Each of the following T lines contains a test case, which consists of a string s and an integer k separated by space. The string contains only lowercase letters and does not include whitespace.

outputFormat

For each test case, output a single line containing the minimum number of changes required to transform s into a palindrome using no more than k changes. If it is not possible, output -1.

## sample

3
abca 1
race 2
abc 0

1
2
-1

</p>