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

• First line: \(t\) denoting the number of test cases
• For each test case (\(2 \times t\) lines):
  • First line: Space-separated integers \(n,\ f,\ k,\ c\) 
  • Second line: A string of size \(n\)

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