Minimum Moves to Achieve K Distinct Characters

You are given a string s and an integer k. Your task is to determine the minimum number of moves required such that the string contains exactly k distinct characters.

In one move, you are allowed to either remove one occurrence of a character or (conceptually) add a new distinct character (if the string length permits). However, note that if k is greater than the length of the string s, it is impossible to have k distinct characters and you should output -1.

The rules are as follows:

• If the number of distinct characters in s is exactly k, no moves are needed.
• If the string contains more than k distinct characters, you need to remove some characters so that only k distinct characters remain. The minimum number of moves in this case is the difference between the current distinct count and k.
• If the string contains fewer than k distinct characters, you need to add new distinct characters. The minimum number of moves is the difference between k and the current distinct count.
• If k is greater than the length of s, output -1 because it is impossible to achieve the target.

Example:

• For s = "abc" and k = 2, the string has 3 distinct characters so you need to remove 1 character. The output is 1.
• For s = "aaa" and k = 1, the string already has 1 distinct character so the output is 0.
• For s = "abcd" and k = 4, the string has exactly 4 distinct characters so the output is 0.
• For s = "abc" and k = 4, since k > len(s), the output is -1.
• For s = "aabbcc" and k = 3, the string already has 3 distinct characters so the output is 0.
• For s = "aabbcc" and k = 1, the string has 3 distinct characters so you need to remove 2 characters. The output is 2.

inputFormat

The input is read from standard input and follows the format below:

T
s1 k1
s2 k2
...
sT kT

Here, T is the number of test cases. For each test case, the first element is the string s (consisting of lowercase letters with no spaces) and the second element is an integer k, separated by a space.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of moves required to make the string contain exactly k distinct characters. If it is impossible to achieve this, output -1.

## sample

6
abc 2
aaa 1
abcd 4
abc 4
aabbcc 3
aabbcc 1

1
0
0
-1
0
2

</p>