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




 
public class Main{
    public static long mod = (long)1e9+7;
    public static ArrayList<Integer>[] graph;
    public static void sort(int[] arr){
        ArrayList<Integer> list = new ArrayList<>(arr.length);
        for(int u:arr) list.add(u);
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
    public static void sort(long[] arr){
        ArrayList<Long> list = new ArrayList<>(arr.length);
        for(long u:arr) list.add(u);
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
    public static void main(String[] args) throws Exception {
        InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
        int t = 1;
         t = in.nextInt();
        for (int i = 0; i < t; i++) {
            solve(in,out);
        }
        out.close();
    }
    static char[] list;
    static long[][] ncr;
    private static void solve(InputReader in, PrintWriter out) {
        int n = in.nextInt();
        //int m = in.nextInt();
        char[] list = in.next().toCharArray();
        int ans1 = -1;
        int ans2 = -1;
        int[] sum = new int[n];
        int i =0;
        int count = 0;
        for(char c:list){
            if(c=='a') count++;
            else count--;
            sum[i++] = count;
        }
        out: for (int j = 0; j < sum.length; j++) {
            for (int j2 = j+1; j2 < sum.length; j2++) {
                if((sum[j2] - (j>=1?sum[j-1]:0))==0){
                    ans1 = j+1;
                    ans2 = j2+1;
                    break out;
                }   
            }
        }
        out.println(ans1+" "+ans2);
    }
    
    
    private static int search(int[] list,int i) {
        int hi = list.length-1;
        int lo = 0;
        int ans = 0;
        while(lo<=hi){
            int mid = lo + (hi-lo)/2;
            if(list[mid]>i){
                ans = mid;
                hi = mid-1;
            }
            else lo = mid+1;
        }
        return ans;
    }
    private static long modpow(long cons, int i) {
        cons%=mod;
        return (((cons*cons)%mod)*cons)%mod;
    }
    private static long calc(long l, long r, int lengtha) {
        long big = (1l<<(lengtha))-1;
        long ans = 0;
        int i = lengtha - 1;
            for (int j = 0; j < i ; j++) {
                long cons = big ^ (1l<<j);
                if(cons>=l && cons<=r){ans += modpow(cons,3);
                if(ans>=mod) ans-=mod;}
            }
            for (int j = 0; j < i; j++) {
                for (int j2 = j+1; j2 < i; j2++) {
                 
                long cons = big ^ (1l<<j) ^(1l<<j2);
                if(cons>=l && cons<=r){ans += modpow(cons,3);
                    if(ans>=mod) ans-=mod;}
                }
            } 
            for (int j = 0; j < i; j++) {
                for (int j2 = j+1; j2 <i; j2++) {
                    for (int k = j2+1; k < i; k++) {     
                        long cons = big ^ (1l<<j) ^(1l<<j2)^(1l<<k);
                        if(cons>=l && cons<=r){ans += modpow(cons,3);
                            if(ans>=mod) ans-=mod;}       
                    }
                }
            }
            return ans; 

    }
    private static long invmod(long i) {
        long pow = mod-2;
        long ans = 1;
        while(pow>0){
            if(pow%2==1) ans  = (ans*i)%mod;
            i = (i*i)%mod;
            pow/=2;
        }
        return ans;
    }
   
}
class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;
 
    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }
 
    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }
 
    public int nextInt() {
        return Integer.parseInt(next());
    }
 
    public long nextLong() {
        return Long.parseLong(next());
    }
    public double nextDouble(){
        return Double.parseDouble(next());
    }
    public int[] readIntArray(int size){
        int[] list = new int[size];
        for(int i = 0;i<size;i++) list[i] = nextInt();
        return list;
    }
    public long[] readLongArray(int size){
        long[] list = new long[size];
        for(int i = 0;i<size;i++) list[i] = nextLong();
        return list;
    }
    public double[] readDoubleArray(int size){
        double[] list = new double[size];
        for(int i = 0;i<size;i++) list[i] = nextDouble();
        return list;
    }
    public String linereader() {
        String s = null;
        try{
            s = reader.readLine();
        }
        catch (IOException e) {
            throw new RuntimeException(e);
        }
        return s;
    }
 
}
class Pair<T extends Comparable<T>,K extends Comparable<K> > implements Comparable<Pair<T,K>>{
    T first;
    K second;
    public Pair(T first, K second){
        this.first  = first;
        this.second = second;
    }
    @Override
    public String toString(){
        return first+" "+second;
    }
    @Override
    public int compareTo(Pair<T,K> o) {
        // TODO Auto-generated method stub
        if((first).compareTo(o.first)!=0) return first.compareTo(o.first);
        else return second.compareTo(o.second);
    }
 
}