Somehow Sharmeen solved the last problem “Sharmeen loves substring” and Mozahid became impressed on her performance. Now Mozahid wants to test her programming skill and gives her the hardest problem of today’s problem set. He will give her a string of lowercase English letters of size N (1 <= N <= 10^5) and an integer X (0 <= X <= 10^12). Sharmeen has to find the largest substring of that string, which has exactly X subsequences of ‘sms’. If multiple solutions exists, she has to select the leftmost one. If no solution exists, she has to print “-1” (without quotes); otherwise, she has to print the starting and ending position of the substring separated by a space in one line. For exact output format, see the example.

N.B. Substring is a consecutive sequence of characters of a string, whereas subsequence does not necessarily need to be consecutive. But for both, you have to maintain the order. For clearance, ‘skmjssm’ has 2 different subsequences of ‘sms’.  {1, 3, 5} and {1, 3, 6} (1 based position).

Input

In first line given number of test cases T (1 <= T <= 10).

For each test case, a string of lowercase English letters of size N (1 <= N <= 10^5) and an integer X (0 <= X <= 10^12) are given, separated by a space.

Output

For each test case, if solution exists, print the starting and ending position of the substring (1 based position) separated by a space, otherwise print “-1” (without quote) in one line .

Example

Input:
2
smsmmsms 1
mmsm 1

Output:
1 5
-1

[ This problem originally written by MD. Mozahidul Islam Bhuiyan(kissu_pari_na) ]