You are given a string s that contains lowercase alphabets. The length of this string is n. While performing an operation, you can rotate the string by one character in the clockwise direction.
The string must satisfy the following condition:
You are given a character c and two integers f and k. Determine the minimum number of operations that you must perform so that the prefix of length k has at least f occurrences of character c.
Note: It may be impossible to make the string satisfy this condition.
Input format
Output format
For each test case, print a single line denoting the required minimum number of rotations if it is possible to satisfy the condition. Otherwise, print −1.
Constraints
1≤t≤101≤n≤1051≤f≤n1≤k≤ncisalowercasealphabet
In the first test case, after 2 clockwise rotations we will get "ilnikh". The prefix of length 4 contains 2 occurences of 'i'.
In the second test case, it is impossible to achive 2 occurences of 'm' in prefiix of length 2 in "momo" after any number of rotations.