In the country of Thuvax lived an old wizard named Chanithpra. He practised a form of magic in which the power of spell came from the letters that were written on a piece of parchment.
When a sentence s is written, the intensity of the letters are as follows:
1. Intensity of 'a' is 1, 'b' is 2 and it continues till 'z' whose intensity is 26.
2. Intensity of 'A' is 51, 'B' is 52 and it continues till 'Z' whose intensity is 76.
3. Intensity of ' '(space) is 32.
 
The power of a spell written as a part of the sentence is equal to the sum of the intensities of the characters present in it modulo m.
 
Chanithpra finds an old parchment in Thuvax with a sentence s written on it.
Help him find the longest spell (i, i+1, ... j) in the sentence s whose power matches with k. (0<=i<=j<length of s)
 
You need to print the starting index i(0<=i<=length-1) of such a spell in the sentence and the length of the spell.  
 
If there are multiple such spells, find the minumum index i and if there is no such spell print -1.

Input

The first line contains a single positive integer t(1<=t<=100) denoting the number of test cases.
Each test case consists of 2 lines:
The first line consists of the sentence s(1<=length of s<=1000000).
The second line consists of two integers m and k (2<=m<=1000007 and 0<=k<m).

Output

For each test case, output one line containing 2 integers. The first is the minimum index i(0<=i<=s.length-1). The second is the length of the spell.
If no such spell is present, print -1

Example

Input:
1
Hello World
10 7
Output:
0 7