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".
import java.util.*;
import java.io.*;

public class A1569 {
	static boolean multipleTC = true;
	FastReader in;
	PrintWriter out;

	static int mod = 1000000007;

	public static void main(String[] args) throws Exception {
		new A1569().run();
	}

	void run() throws Exception {
		in = new FastReader();
		out = new PrintWriter(System.out);
		int T = (multipleTC) ? ni() : 1;
		pre();
		for (int t = 1; t <= T; t++)
			solve(t);
		out.flush();
		out.close();
	}

	void pre() throws Exception {
	}

	void solve(int TC) throws Exception {
		int n = ni();
		String str = nln();
		if (n <= 1) {
			pn("-1 -1");
			return;
		}
		
		for (int i = 0; i < n - 1; i++) {
			if (str.charAt(i) != str.charAt(i + 1)) {
				pn((i+1) + " " + (i + 2));
				return;
			}
		}
		pn("-1 -1");

	}

	static int bitCount(int x) {
		return x == 0 ? 0 : (1 + bitCount(x & (x - 1)));
	}

	static void dbg(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}

	public static boolean isPrime(long n) {
		if (n < 2)
			return false;
		if (n == 2 || n == 3)
			return true;
		if (n % 2 == 0 || n % 3 == 0)
			return false;
		long sqrtN = (long) Math.sqrt(n) + 1;
		for (long i = 6L; i <= sqrtN; i += 6) {
			if (n % (i - 1) == 0 || n % (i + 1) == 0)
				return false;
		}
		return true;
	}

	public static long gcd(long a, long b) {
		if (a > b)
			a = (a + b) - (b = a);
		if (a == 0L)
			return b;
		return gcd(b % a, a);
	}

	public long pow(long base, long exp, long MOD) {
		base %= MOD;
		long res = 1;
		while (exp > 0) {
			if ((exp & 1) == 1)
				res = res * base % MOD;
			base = base * base % MOD;
			exp >>= 1;
		}
		return res;
	}

	public static long totient(long n) {
		long result = n;
		for (int p = 2; p * p <= n; ++p)
			if (n % p == 0) {
				while (n % p == 0)
					n /= p;
				result -= result / p;
			}
		if (n > 1)
			result -= result / n;
		return result;
	}

	int bit(long n) {
		return (n == 0) ? 0 : (1 + bit(n & (n - 1)));
	}

	public long max(long... arr) {
		long max = arr[0];
		for (long itr : arr)
			max = Math.max(max, itr);
		return max;
	}

	public int max(int... arr) {
		int max = arr[0];
		for (int itr : arr)
			max = Math.max(max, itr);
		return max;
	}

	public long min(long... arr) {
		long min = arr[0];
		for (long itr : arr)
			min = Math.min(min, itr);
		return min;
	}

	public int min(int... arr) {
		int min = arr[0];
		for (int itr : arr)
			min = Math.min(min, itr);
		return min;
	}

	public long sum(long... arr) {
		long sum = 0;
		for (long itr : arr)
			sum += itr;
		return sum;
	}

	public long sum(int... arr) {
		long sum = 0;
		for (int itr : arr)
			sum += itr;
		return sum;
	}

	void p(Object o) {
		out.print(o);
	}

	void pn(Object o) {
		out.println(o);
	}

	void pni(Object o) {
		out.println(o);
		out.flush();
	}

	String n() throws Exception {
		return in.next();
	}

	String nln() throws Exception {
		return in.nextLine();
	}

	int ni() throws Exception {
		return Integer.parseInt(in.next());
	}

	long nl() throws Exception {
		return Long.parseLong(in.next());
	}

	double nd() throws Exception {
		return Double.parseDouble(in.next());
	}

	class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastReader(String s) throws Exception {
			br = new BufferedReader(new FileReader(s));
		}

		String next() throws Exception {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new Exception(e.toString());
				}
			}
			return st.nextToken();
		}

		String nextLine() throws Exception {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				throw new Exception(e.toString());
			}
			return str;
		}
	}
}