In the country of Thuvax lived an old wizard named Chanithpra. He practiced 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 until 'z' whose intensity is 26.
2. Intensity of 'A' is 51, 'B' is 52 and it continues until '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 minimum 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