Minimum Changes to Palindrome

You are given a string S and an integer N. Your task is to determine the minimum number of character changes required to transform the string into a palindrome, under the constraint that you are allowed at most N operations. A single operation consists of changing one character to any other character.

If the minimum number of changes required is less than or equal to N, output that minimum number; otherwise, output -1.

Note: The operation count N is an upper bound; you do not need to use all the operations if fewer changes can make the string a palindrome.

For example:

• For S = "abc" and N = 2, only one change is required (change 'c' to 'a' or 'a' to 'c'), so the answer is 1.
• For S = "abcd" and N = 1, at least two changes are needed, so the answer is -1.

inputFormat

The first line contains an integer T representing the number of test cases.

Each of the next T lines contains a non-empty string S and an integer N separated by a space.

Constraints:

• The string S consists of lowercase or uppercase letters.
• N is a non-negative integer.

outputFormat

For each test case, output in a new line a single integer: the minimum number of changes required to convert the given string S into a palindrome under the allowed number of operations. If it is not possible, output -1.

## sample

1
racecar 1

0

</p>