Bob is given a string \(S\) of length \(N\) consisting of lowercase English letters. He has given you a task to distribute all the substrings of this string to all the students in the class. It is given that the number of students in a class is the same as the number of substrings of the given string. But there is a problem that any two students must not have the same string.

Help Bob to find the minimum number of characters in the string that needs to be changed so that each student gets the unique string, or print \(-1\) if it is impossible to do so.

Input Format

The first line contains an integer \(T\), which denotes the number of test cases.
The first line of each test case contains an integer \(N\), denoting the length of the string \(S\).
The second line of each test case contains the string \(S\).

Output Format

For each test case, print the minimum number of changes required to make all the substrings of the string distinct or print \(-1\) if you can't make it.

Constraints

\(1 \leq T \leq 10 \\ 1 \leq N \leq 10^5\)