[Solved] Balanced Substring solution codeforces

Balanced Substring solution codeforces


You are given a string ss, consisting of nn letters, each letter is either ‘a‘ or ‘b‘. The letters in the string are numbered from 11 to nn.

s[l;r]s[l;r] is a continuous substring of letters from index ll to rr of the string inclusive.

A string is called balanced if the number of letters ‘a‘ in it is equal to the number of letters ‘b‘. For example, strings “baba” and “aabbab” are balanced and strings “aaab” and “b” are not.

Find any non-empty balanced substring s[l;r]s[l;r] of string ss. Print its ll and rr (1lrn1≤l≤r≤n). If there is no such substring, then print 1−1 1−1.

Input

The first line contains a single integer tt (1t10001≤t≤1000) — the number of testcases.

Then the descriptions of tt testcases follow.

The first line of the testcase contains a single integer nn (1n501≤n≤50) — the length of the string.

The second line of the testcase contains a string ss, consisting of nn letters, each letter is either ‘a‘ or ‘b‘.

Output

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

Example Balanced Substring solution codeforces
input Balanced Substring solution codeforces

Copy Balanced Substring solution codeforces
4
1
a
6
abbaba
6
abbaba
9
babbabbaa
output

Copy
-1 -1
1 6
3 6
2 5
Note

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“.


Solution: Click here


Also read : Airline Restrictions codechef solution

Balanced Substring solution codeforces

Leave a Comment

Your email address will not be published. Required fields are marked *