#include <bits/stdc++.h>
using namespace std;
namespace kira {
template <class T>
using v = vector<T>;
template <class T>
using vv = vector<vector<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
const long double pi = acos(-1.0);
const long long dx[4] = {0, 1, 0, -1};
const long long dy[4] = {1, 0, -1, 0};
const long long dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const long long dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const long long INF = (long long)1e18 + 100;
const long long MINF = (long long)-1e17 + 100;
const long long MOD = (long long)1e9 + 7;
}  // namespace kira
using namespace kira;
const long long N = (long long)(2e5 + 7);
void init() {}
void solve(long long test_case) {
  long long n;
  cin >> n;
  string s;
  cin >> s;
  map<long long, long long> mp;
  long long cur = 0;
  mp[0] = 0;
  for (long long i = 0; i < n; i++) {
    if (s[i] == 'a') {
      cur++;
    } else {
      cur--;
    }
    if (mp.count(cur)) {
      cout << mp[cur] + 1 << " " << i + 1 << endl;
      return;
    }
    mp[cur] = i + 1;
  }
  cout << -1 << " " << -1 << endl;
}
int32_t main() {
  long long tt = (long long)clock();
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  init();
  long long t = 1;
  if (1) cin >> t;
  for (long long i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

You are given a string s, consisting of n letters, each letter is either 'a' or 'b'. The letters in the string are numbered from 1 to n.

s[l; r] is a continuous substring of letters from index l to r 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] of string s. Print its l and r (1 ≤ l ≤ r ≤ n). If there is no such substring, then print -1 -1.

Input

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

Then the descriptions of t testcases follow.

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

The second line of the testcase contains a string s, consisting of n 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], then print l r (1 ≤ l ≤ r ≤ n). Otherwise, print -1 -1.

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-empty balanced subtrings.

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
namespace kira {
template <class T>
using v = vector<T>;
template <class T>
using vv = vector<vector<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ", ";
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  long long f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
const long double pi = acos(-1.0);
const long long dx[4] = {0, 1, 0, -1};
const long long dy[4] = {1, 0, -1, 0};
const long long dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const long long dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const long long INF = (long long)1e18 + 100;
const long long MINF = (long long)-1e17 + 100;
const long long MOD = (long long)1e9 + 7;
}  // namespace kira
using namespace kira;
const long long N = (long long)(2e5 + 7);
void init() {}
void solve(long long test_case) {
  long long n;
  cin >> n;
  string s;
  cin >> s;
  map<long long, long long> mp;
  long long cur = 0;
  mp[0] = 0;
  for (long long i = 0; i < n; i++) {
    if (s[i] == 'a') {
      cur++;
    } else {
      cur--;
    }
    if (mp.count(cur)) {
      cout << mp[cur] + 1 << " " << i + 1 << endl;
      return;
    }
    mp[cur] = i + 1;
  }
  cout << -1 << " " << -1 << endl;
}
int32_t main() {
  long long tt = (long long)clock();
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(10);
  init();
  long long t = 1;
  if (1) cin >> t;
  for (long long i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}

```