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.

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

input

Copy
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

C++ Solution

#include <bits/stdc++.h>

using namespace std;

 

 

#define ff(a, c) for (int(a) = 0; (a) < (c); (a)++)

 

#define w(x) int x; cin >> x; while(x–)

 

int32_t main() {

 

w(t) {

int n;

cin >> n;

 

string s;

cin >> s;

 

// cout << s << endl;

int a = 0, b = 0;

ff(i, n) {

// cout << s[i] << endl;

if (s[i] == ‘a’) a++;

else b++;

}

 

if (a == 0 or b == 0) cout << “-1” << ” “ << “-1” << endl;

else {

ff(i, n – 1) {

if (s[i] == ‘a’ and s[i + 1] == ‘b’) {

cout << i + 1 << ” “ << i + 2 << endl;

break;

}

else if (s[i] == ‘b’ and s[i + 1] == ‘a’) {

cout << i + 1 << ” “ << i + 2 << endl;

break;

}

}

}

}

}

C++ Alternate Solution

#include <iostream>

#include<bits/stdc++.h>

using namespace std;

 

int main() {

 

int T;

cin>>T;

 

while(T–)

{

int n;

cin>>n;

string s;

cin>>s;

bool res=false;

if(n<=1)

{cout<<“-1”<<” “<<“-1”<<endl;

res=true;

}

 

 

 

for(int i=0;i<n-1;i++)

{

if(s[i]!=s[i+1])

{

cout<<i+1<<” “<<i+2<<endl;

res=true;

break;

}

}

if(res==false)

cout<<“-1”<<” “<<“-1”<<endl;

 

}

return 0;

}


Also read : Balanced Substring solution codeforces

Leave a Comment