The second line of the testcase contains a string s,
consisting of n letters , each letter is either ’a’ or
’b ’.

For each testcase print two integers . If there is an
adjacent pair of non - identical letters at indexes l
and r, print l, r. Otherwise , print -1 -1.

For each testcase print two integers . If there exists
a non - empty balanced substring s[l; r], then print l
r (1 <= l <= r <= n). Otherwise , print -1 -1.

Output

Example

Input

4
1
a
6
abbaba
6
abbaba
9
babbabbaa

Output

-1 -1
1 6
3 6
2 5

Note

In the first testcase there are no non - identical
pairs .

In the second and third testcases there are non -
identical pairs .

In the first testcase there are no non - empty balanced
subtrings .

In the second and third testcases there are multiple
balanced substrings , including the entire string "
abbaba " and substring " baba ".

Output

Example

Input

4
1
a
6
abbaba
6
abbaba
9
babbabbaa

Output

-1 -1
1 6
3 6
2 5

Note

71
alphacode