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≤T≤101≤N≤105
For test case 1: Substrings will be a,b,c,ab,bc,abc. All substrings are distinct. No changes are required. Hence, the answer is 0.
For test case 2: Substrings will be x,x,y,z,xx,xy,yz,xxy,xyz,xxyz. You can see substrings are not distinct. You can change the character at index 1 to some other character (1-based indexing). Like S=bxyz. Hence, the answer is 1.
