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

public class Main {

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;

        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(
                    new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    } else {
                        continue;
                    }
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0,
                    BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }
//
//

    //    static class TreeNode {
//        int val;
//        TreeNode left,right;
//        TreeNode(int val){
//            this.val=val;left=null;right=null;
//        }
//    }
//
//   static void sieveOfEratosthenes(int n)
//    {
//        boolean prime[] = new boolean[n + 1];
//        for (int i = 0; i <= n; i++)
//            prime[i] = true;
//
//        for (int p = 2; p * p <= n; p++)
//        {
//            if (prime[p] == true)
//            {
//                for (int i = p * p; i <= n; i += p)
//                    prime[i] = false;
//            }
//        }
//
//        for (int i = 2; i <= n; i++)
//        {
//            if (prime[i] == true)
//                treeMap.put(i,0);
//        }
//    }
//    static TreeMap<Integer,Integer> treeMap;
//    static class comp implements Comparator<Point> {
//        public int compare(Point a, Point b) {
//            if (b.y == a.y) {
//                return a.x - b.x;
//            }
//            return b.y - a.y;
//        }
//    }

    static boolean ff = false;

    //    static void maxx(int ind,int l,int r,int d,int u,int n)
//    {
//        if(ind==4){
//            if(l<0 || r<0 || u<0 || d<0){
//                return;
//            }
//            ff=true;
//            return;
//        }
//        if(ind==0){
//            if(l==n){
//                maxx(ind+1,l-2,r,d-1,u-1,n);
//            }else if(l==n-1){
//                maxx(ind+1,l-1,r,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l-1,r,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else if(ind==1){
//            if(r==n){
//                maxx(ind+1,l,r-2,d-1,u-1,n);
//            }else if(r==n-1){
//                maxx(ind+1,l,r-1,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else if(ind==2){
//            if(d==n){
//                maxx(ind+1,l-1,r-1,d-2,u,n);
//            }else if(d==n-1){
//                maxx(ind+1,l-1,r,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d-1,u,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else{
//            if(u==n){
//                maxx(ind+1,l-1,r-1,d,u-2,n);
//            }else if(u==n-1){
//                maxx(ind+1,l-1,r,d,u-1,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//        }
//    }
//    static void filereader() throws IOException{
//        FileReader fileReader=new FileReader("input.txt");
//        int ch;
//        String str="";
//        StringBuilder stringBuilder=new StringBuilder();
//        while ((ch=fileReader.read())!=-1)
//            stringBuilder.append((char)ch);
//
//        fileReader.close();
//        StringBuilder ans=new StringBuilder();
//        FileWriter fw=new FileWriter("output.txt");
//        for(int j=0;j<ans.length();j++){
//            fw.write(ans.charAt(j));
//        }
//        fw.close();
//    }
//    static class point {
//        int w, v;
//
//        point(int v, int w) {
//            this.v = v;
//            this.w = w;
//        }
//    }
//
//    static class compp implements Comparator<point> {
//        public int compare(point a, point b) {
//            return b.v - a.v;
//        }
//    }

    //    static int cal(int ind,String s,String x,int val){
//        if(ind>=s.length()){
//            if(val%7==0){
//                return 1;
//            }else{
//                return 0;
//            }
//        }
//        if(aa[ind][val]!=-1){
//            return aa[ind][val];
//        }
//
//        if(x.charAt(ind)=='A'){
//            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
//            return aa[ind][val]=Math.min( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
//        }else{
//            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
//            return aa[ind][val]=Math.max( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
//        }
//
//    }
//    static int aa[][];

    //    static long calculateWays(int ind,int bit,int[] primes,long a,long b,int[] flags){
//
//        long num=(long)((long)ind+(long)a);
//        if(num>b){
//            return 1;
//        }
//        if(aaa[ind][bit]!=-1){
//            return aaa[ind][bit];
//        }
//
//        long tot=0;
////        int flag=0;
////        int bitt=bit;
////        for(int j=0;j<primes.length;j++){
////            int jj= (int)bit & (int)Math.pow(2,j);
////
////            if(jj!=0 && num%(long)primes[j]==0 ){
////                flag=1;
////                break;
////            }
////            if( num%(long)primes[j]==0 ){
////                bitt=(int)bitt | (int)Math.pow(2,j);
////
////            }
////        }
//        int jj=(int)(flags[ind] & (int)bit);
//        if( jj==0){
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit | flags[ind],primes,a,b,flags));
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit,primes,a,b,flags));
//
//        }else{
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit,primes,a,b,flags));
//        }
//
//        return aaa[ind][bit]=tot;
//    }
//    static long[][] aaa;
//
//    static long maxx(String str, int n, long val) {
//
//        if (hashMap.get(str) != null) {
//            return hashMap.get(str);
//        }
//        long tot = 0;
//        if (str.equals("")) {
//            for (int j = 1; j <= 9; j++) {
//                tot = tot + maxx(str + String.valueOf(j), n, val);
//            }
//            hashMap.put(str, tot);
//
//            return tot;
//        } else {
//            String ss = str + str;
//            if (Long.parseLong(ss) > val) {
//                return 0;
//            }
//            if (str.length() == n) {
//                return 1;
//            }
//            for (int j = 0; j <= 9; j++) {
//                tot = tot + maxx(str + String.valueOf(j), n, val);
//            }
//            hashMap.put(str, tot);
//            return tot;
//        }
//
//    }
//
//    static class poi {
//        int freq, occur, num;
//
//        poi(int freq, int occur, int num) {
//            this.freq = freq;
//            this.num = num;
//            this.occur = occur;
//        }
//    }
//
//    static class poii {
//        int day, tot;
//
//        poii(int day, int tot) {
//            this.day = day;
//            this.tot = tot;
//        }
//    }
//
//    static class comp2 implements Comparator<poii> {
//        public int compare(poii a, poii b) {
//            return a.tot - b.tot;
//        }
//    }
//
//    static class comp1 implements Comparator<poi> {
//        @Override
//        public int compare(poi o1, poi o2) {
//            if (o2.occur == o1.occur) {
//                return o1.freq - o2.freq;
//            }
//            return o1.occur - o2.occur;
//        }
//    }

    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

//    static HashMap<String, Long> hashMap;

//    static class poit {
//        int freq, val;
//
//        poit(int freq, int val) {
//            this.freq = freq;
//            this.val = val;
//        }
//    }

//    static class com implements Comparator<poit> {
//        public int compare(poit a, poit b) {
//            return b.freq - a.freq;
//        }
//    }


//    static int maxx(int ind,String str,int prev,int x,int y){
//        if(ind>=str.length()){
//            return 0;}
//        if(aa[ind][prev]!=Integer.MAX_VALUE){
//            return aa[ind][prev];}
//        if(str.charAt(ind)=='?' ){
//            if(ind>0){
//                if(prev==1){
//                    if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
//                             return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x+y );
//
//                    }
//                    else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
//                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x,maxx(ind+1,str,2,x,y)+x );
//
//                    }
//                    else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
//                        return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x );
//                    }
//                    else{
//                        return aa[ind][prev]=Math.min(maxx( ind+1,str,1,x,y ),maxx(ind+1,str,2,x,y)+x);
//                    }
//
//                }
//                else{
//                    if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
//                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+y,maxx(ind+1,str,2,x,y)+y );
//
//                    }
//                    else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
//                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x+y,maxx(ind+1,str,2,x,y) );
//
//                    }
//                    else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
//                        return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y)+y,maxx(ind+1,str,2,x,y) );
//                    }
//                    else{
//                        return aa[ind][prev]=Math.min(maxx( ind+1,str,1,x,y )+y,maxx(ind+1,str,2,x,y));
//                    }
//                }
//            }
//            else{
//                if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
//                    return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x );
//
//                }
//                else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
//                    return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x,maxx(ind+1,str,2,x,y) );
//
//                }
//                else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
//                    return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y) );
//                }
//                else{
//                    return aa[ind][prev]=0;
//                }
//            }
//        }else if(str.charAt(ind)=='C'){
//            if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
//                return aa[ind][prev]=maxx(ind+1,str,1,x,y);
//
//            }
//            else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
//                return aa[ind][prev]=maxx(ind+1,str,1,x,y)+x;
//
//            }
//            else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
//                return aa[ind][prev]=  maxx(ind+1,str,1,x,y);
//            }
//            else{
//                return aa[ind][prev]=0;
//            }
//        }
//        else{
//            if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
//                return aa[ind][prev]=maxx(ind+1,str,2,x,y)+y;
//
//            }
//            else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
//                return aa[ind][prev]=maxx(ind+1,str,2,x,y);
//
//            }
//            else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
//                return aa[ind][prev]=  maxx(ind+1,str,2,x,y);
//            }
//            else{
//                return aa[ind][prev]=0;
//            }
//        }
//    }
//    static int[][] aa;
//    static int totalCost(int[] arr,int[] arr1,int n){
//        HashMap<Integer,Integer> has=new HashMap<>();
//        for(int i=0;i<n;i++){
//
//            has.put(arr[i],i );
//
//        }
//        Arrays.sort(arr1);
//        int tot=0;
//        for(int i=0;i<n-1;i++){
//            tot=tot+has.get(arr1[i])-i+1;
//            int tta=has.get(arr1[i]);
//            for(int j=tta;j>=i;j-- ){
//                has.put(arr[j],tta-j+i );
//
//            }
//            int low=i;
//            int high=tta;
//            while(low<high){
//                int temp=arr[low];
//                arr[low]=arr[high];
//                arr[high]=temp;
//                low++;high--;
//            }
//
//        }
//        return tot;
//
//    }
//    static boolean fff=false;
//    static HashSet<String> hashSet=new HashSet<>();
//    static void maxx(int ind,int[] arr,HashSet<Integer> has,int n,String str,int cost){
//        if(ind==n){
//            int to=totalCost(arr,arr,n);
//            if(to==cost){
//                fff=true;
//            }
//            return;
//        }
//        if(hashSet.contains(str)){
//            return ;
//        }
//        for(int j=1;j<=n;j++){
//            if(!has.contains(j)){
//                arr[ind]=j;
//                has.add(j);
//                maxx(ind+1,arr,has,n,str+String.valueOf(j),cost);
//                has.remove(j);
//            }
//            if(ff){
//                return;
//            }
//        }
//    }
//    static long maxx(int ind,int n,int flag,int k){
//        if(ind>n || ind<0 || k==1){
//            return 0;
//        }
//        if(flag==1 && ind==0){
//            return 0;
//        }
//        if(aaaa[ind][flag][k]!=-1) {
//            return aaaa[ind][flag][k];
//        }
//        if(flag==0){
//            return aaaa[ind][flag][k]=(long)(maxx(ind-1,n,1,k-1)+(long)1+maxx(ind+1,n,0,k))%(long)mod;
//        }
//        else{
//            return aaaa[ind][flag][k]=(long)(maxx(ind+1,n,0,k-1)+(long)1+maxx(ind-1,n,1,k))%(long)mod;
//        }
//
//    }
//
////    static int minimum_change(int ind,int[] arr,int tot,int flag,String str,String temp){
////        if(ind>=arr.length){
////            return 0;
////        }
////        if(tot>=5) {
////            String strr=String.valueOf(arr[ind]);
////            for(int j=0;j<=9;j++) {
////                strr=strr.concat(String.valueOf(j));
////            }
////        }
////    }
//
//    static long[][][] aaaa;
//    static long mod=(long)((long)Math.pow(10,9)+(long)7);
//    static List<Integer> ans=new ArrayList<>();
//    static void goodVertices(LinkedList<Integer>[] linkedLists,int src,int parent,HashSet<Integer> hashSet,int[] cost){
//
//        int flag=0;
//        if(!hashSet.contains(cost[src])){
//            hashSet.add(cost[src]);
//            ans.add(src+1);
//            flag=1;
//        }
//        for(Integer i:linkedLists[src]){
//            if(i==parent){
//                continue;
//            }
//            goodVertices(linkedLists,i,src,hashSet,cost);
//        }
//        if(flag==1){
//            hashSet.remove(cost[src]);
//        }
//
//    }
//    static boolean fla=false;
//    static void calculate(String[] str,int flag,String str1,String str2){
//        if(flag==0){
//            if(str[0].length()==str1.length()){
//                calculate(str,1,str1,str2);
//                return;
//            }
//            for(int j=0;j<=9;j++){
//                if( j==0 && str1.equals("") ){
//                    continue;
//                }
//                calculate(str,1,str1+String.valueOf(j),str2);
//                if(fla){
//                    break;
//                }
//            }
//        }
//        else if(flag==1){
//            if(str[1].length()==str2.length()){
//                calculate(str,2,str1,str2);
//                return;
//            }
//            int ind=str2.length();
//            if( str[0].length()>ind && str[0].charAt(ind)==str[1].charAt(ind)){
//                calculate(str,1,str1,str2+String.valueOf(str1.charAt(ind)));
//            }else{
//                for(int j=0;j<=9;j++){
//                    if(j==0 && str2.equals("")){
//                        continue;
//                    }
//                    calculate(str,1,str1,str2+String.valueOf(j));
//                }
//            }
//        }
//        else{
//            long n1=Long.parseLong(str1);
//            long n2=Long.parseLong(str2);
//            long n3=(long)((long)n1+(long)n2);
//            if(String.valueOf(n3).length()==str[2].length()){
//
//            }
//
//        }
//    }
//static List<Integer> findprime(int n) {
//    List<Integer> primes = new ArrayList<>();
//    boolean[] prime = new boolean[n];
//    for (int j = 1; j < prime.length; j++) {
//        prime[j] = true;
//    }
//    for (int j = 2; j * j < prime.length; j++) {
//        if (!prime[j]) {
//            continue;
//        }
//        for (int i = j * j; i < prime.length; i = i + j) {
//            prime[i] = false;
//        }
//    }
//    for (int j = 2; j < prime.length; j++) {
//        if (prime[j]) {
////            String str=String.valueOf(j);
////            hashMap1.putIfAbsent(str.length(),new ArrayList<>());
////            hashMap1.get(str.length()).add(j);
//            primes.add(j);
//        }
//    }
//    return primes;
//}
//    static long[][] dp;
//        static long calculatemin(int low,int high,int[] arr,int flag,long tot){
//            if(dp[low][high]!=-1){
//                return dp[low][high];
//            }
//            if( low==high){
//                return 0;
//            }
//            return dp[low][high]=Math.min( calculatemin(low+1,high,arr,0,tot),
//                    calculatemin(low,high-1,arr,0,tot)  )+(long)( (long)arr[high]-(long)arr[low] );
//        }


//        static List<long[]> list=new ArrayList<>();
//        static HashMap<Integer,List<long[]>> hashMap1;
//        static void maxx( int src,int parent,LinkedList<Integer>[] lin,HashMap<Point,long[]> hashMap  ){
//            List<long[]> list1= new ArrayList<>();
//            list1.addAll(list);
////            System.out.println(list1);
//            hashMap1.put(src,list1);
//            for(Integer i:lin[src]){
//                if(i==parent){
//                    continue;
//                }
//                list.add(hashMap.get(new Point(src,i)));
//                maxx(i,src,lin,hashMap);
//                list.remove(list.size()-1);
//            }
//        }
//    static class com1 implements Comparator<long[]>{
//            public int compare(long[] a,long[] b){
//                return Long.compare(b[2],a[2]);
//            }
//    }
//    static boolean isFla=false;
//    static int maxx(int ind,int[] arr,int sum){
//        if(sum==0){
//            isFla=true;
//            return 0;
//        }
//            if(ind>=arr.length || sum<0){
//                return 0;
//            }
//
//            if(pp[ind][sum] != -1){
//                return pp[ind][sum];
//            }
//        maxx(ind+1,arr,sum-arr[ind]);
//            if(isFla){
//                return 0;
//            }
//
//            return pp[ind][sum]=maxx(ind+1,arr,sum);
//
//    }
//    static int[][] pp;
//    static int maxx(int ind,int[] arr,int sum,int i){
//
//        if(sum==0){
//            isFla=true;
//            return 0;
//        }
//        if(ind>=arr.length || sum<0){
//            return 0;
//        }
//
//        if(pp[ind][sum] != -1){
//            return pp[ind][sum];
//        }
//        if(ind==i){
//            return pp[ind][sum]=maxx(ind+1,arr,sum,i);
//        }
//        maxx(ind+1,arr,sum-arr[ind],i);
//        if(isFla){
//            return 0;
//        }
//
//        return pp[ind][sum]=maxx(ind+1,arr,sum,i);
//
//    }
//     static int[] st;
//    public static int[] constructSegmentTree(int[] arr)
//    {
//        int height = (int)Math.ceil(Math.log(arr.length)/Math.log(2));
//        int size = 2*(int)Math.pow(2, height)-1;
//        st = new int[size];
//        constructST(arr, 0, arr.length-1, 0);
//        return st;
//    }
//
//    public static int constructST(int[] arr, int ss,
//                                  int se, int si)
//    {
//        if (ss==se)
//        {
//            st[si] = arr[ss];
//            return st[si];
//        }
//        int mid = ss+(se-ss)/2;
//        st[si] = gcd(constructST(arr, ss, mid, si*2+1),
//                constructST(arr, mid+1, se, si*2+2));
//        return st[si];
//    }
//
//    // Function to find gcd of 2 numbers.
//    private static int gcd(int a, int b)
//    {
//        if (a < b)
//        {
//            // If b greater than a swap a and b
//            int temp = b;
//            b = a;
//            a = temp;
//        }
//
//        if (b==0)
//            return a;
//        return gcd(b,a%b);
//    }
//
//    public static int findRangeGcd(int ss, int se, int[] arr)
//    {
//        int n = arr.length;
//
//        if (ss<0 || se > n-1 || ss>se)
//            throw new IllegalArgumentException("Invalid arguments");
//
//        return findGcd(0, n-1, ss, se, 0);
//    }
//
//    public static int findGcd(int ss, int se, int qs, int qe, int si)
//    {
//        if (ss>qe || se < qs)
//            return 0;
//
//        if (qs<=ss && qe>=se)
//            return st[si];
//
//        int mid = ss+(se-ss)/2;
//
//        return gcd(findGcd(ss, mid, qs, qe, si*2+1),
//                findGcd(mid+1, se, qs, qe, si*2+2));
//    }
//
//    static class po{
//        int id;
//        int val;
//        po(int id,int val){
//            this.id=id;
//            this.val=val;
//        }
//    }
//    static class compara implements Comparator<po>{
//        public int compare(po a,po b){
//            return b.val-a.val;
//        }
//    }

//    static boolean[] vis;
//    static boolean[] origvis;
//    static boolean[] colr;
//    static boolean[] colb;
//    static boolean[] colg;
//    static int tot=0;
//    static int[] colo;
//    static long coloring(int src,LinkedList<Integer>[] lin,int color,int n){
//        tot++;
//        origvis[src]=true;
//        if(color==1){
//            colr[src]=true;
//        }else if(color==2){
//            colb[src]=true;
//        }else{
//            colg[src]=true;
//        }
//        vis[src]=true;
//        colo[src]=color;
//        boolean flag=false;
//        long tott=(long)0;
//        for(Integer j:lin[src]){
//            if(!vis[j] ){
//
//                HashSet<Integer> hashSet=new HashSet<>();
//                for(Integer i:lin[j]){
//                    hashSet.add(colo[i]);
//                }
//                hashSet.add(color);
//                for(int i=1;i<=3;i++){
//                    if(!hashSet.contains(i)  ){
//                        if(i==1 && !colr[j]) {
//                            flag = true;
//                            tott = (long) ((long) tott + (long) coloring(j, lin, i, n));
//                        }
//                        else if( i==2 && !colb[j] ){
//                            flag = true;
//                            tott = (long) ((long) tott + (long) coloring(j, lin, i, n));
//
//                        }else if(i==3 && !colg[j]){
//                            flag = true;
//                            tott = (long) ((long) tott + (long) coloring(j, lin, i, n));
//
//                        }
//                    }
//                }
//
//            }
//        }
//        vis[src]=false;
//        colo[src]=0;
//        tot--;
//        if(!flag){
//            return 1;
//        }
////        System.out.println(tott);
//        return tott;
//    }

//    static int maxx(int ind,int[] a,int[] b,int[] c,int[] d,int[] e){
//        if(ind>=a.length){
//            return 0;
//        }
//
//
//    }
//FileWriter fr=new FileWriter("/home/vaibhav/Desktop/output.txt");
//    String str="my name is vaibhav kumar";
//        for(int j=0;j<str.length();j++){
//        fr.write(str);
//        fr.write("\n");
//    }
//        fr.close();
//    //        int[] arr=new int[]{1,2,3,42,53};
////        for(int j=0;j<arr.length;j++){
////            fr.write(String.valueOf(arr[j]));
////        }
////        fr.close();
////        FileReader fileReader=new FileReader("/home/vaibhav/Desktop/output.txt");
//    StringBuilder stringBuilder=new StringBuilder();
//    //        int ch;
////        while((ch=fileReader.read())!=-1){
////            stringBuilder.append((char)ch);
////        }
////        fileReader.close();
//    BufferedReader br=new BufferedReader(new FileReader(new File("/home/vaibhav/Desktop/output.txt")));
//    String st;
//        while ( (st=br.readLine())!=null ){
////            stringBuilder.append(st);
//        System.out.println(st);
//    }
////        System.out.println(stringBuilder.toString());


    static class point {
        int val;
        String name;

    }

    static class comp implements Comparator<point> {
        public int compare(point a, point b) {
            return a.val - b.val;
        }
    }

    // static HashSet<String> hashSet;
//    static void maxx(int tot, List<Character> comp, List<Character> prob, String str ){
//        if(tot==4 ){
//            HashSet<Character> ch=new HashSet<>();
//            for(int j=0;j<4;j++){
//                ch.add(str.charAt(j));
//            }
//            for(Character chh:comp){
//                   if(!ch.contains(chh)){
//                       return ;
//                   }
//            }
//            hashSet.add(str);
//            return ;
//        }
//
//        for(int j=0;j<comp.size();j++){
//            maxx(tot+1,comp,prob,str+String.valueOf(comp.get(j)));
//        }
//        for(int j=0;j<prob.size();j++){
//            maxx(tot+1,comp,prob,str+String.valueOf(prob.get(j)));
//        }
//        return;
//
//    }
//static int[][][] aa;
//    static int maxx(int x,int y,List<String> lis,int flag){
//        if(aa[x][y][flag]!=Integer.MIN_VALUE){
//            return aa[x][y][flag];
//        }
//        if(flag==0){
//            int max=Integer.MIN_VALUE;
//            if( x+1<lis.size()  ){
//                if( lis.get(x+1).charAt(y)=='+' ){
//                max=Math.max( maxx(x+1,y,lis,1 )+1,max );}
//                else{
//                    max=Math.max( maxx(x+1,y,lis,1)-1,max );
//                }
//            }
//            if(y+1< lis.get(0).length() ){
//                if( lis.get(x).charAt(y+1)=='+' ){
//                    max=Math.max( maxx(x,y+1,lis,1 )+1,max );}
//                else{
//                    max=Math.max( maxx(x,y+1,lis,1)-1,max );
//                }
//            }
//            if(max==Integer.MIN_VALUE){
//                return aa[x][y][flag]=0;
//            }
//            return aa[x][y][flag]=max;
//
//        }else{
//            int max=Integer.MAX_VALUE;
//            if( x+1<lis.size()  ){
//                if( lis.get(x+1).charAt(y)=='+' ){
//                    max=Math.min( maxx(x+1,y,lis,0 )-1,max );
//                }
//                else{
//                    max=Math.min( maxx(x+1,y,lis,0)+1,max );
//                }
//            }
//            if(y+1< lis.get(0).length() ){
//                if( lis.get(x).charAt(y+1)=='+' ){
//                    max=Math.min( maxx(x,y+1,lis,0 )-1,max );}
//                else{
//                    max=Math.min( maxx(x,y+1,lis,0)+1,max );
//                }
//            }
//            if(max==Integer.MAX_VALUE){
//                return aa[x][y][flag]=0;
//            }
//            return aa[x][y][flag]=max;
//        }
//
//    }
//static class compp implements Comparator<int[]>{
//    public int compare(int[] a,int[] b){
//        return a[2]-b[2];
//    }
//}
//
//static int maxx(int j){
//    if(j>1){
//        j=maxx(j/10)+maxx(j%10);
//
//    }else{
//        j=0;
//    }
//    return j;
//}
//    static long maxx(int flag,int ind,String str,int k,int n){
//       if(ind>=n){
//           return 1;
//       }
//       if(aa[ind][flag]!=-1){
//           return aa[ind][flag];
//       }
//       if(flag==0){
////           int mm = Math.min(k,str.charAt(ind)-'0');
////           mm = Math.min(mm,str.charAt(str.length()-1-ind)-'0');
//           long tot=maxx(0,ind+1,str,k,n)%mod;
//           for(int j=0;j<k;j++){
//               int ch = str.charAt(ind)-'0';
//               int ch1 = str.charAt(str.length()-1-ind)-'0';
//               if(k>ch){
//                   break;
//               }
//               if(k<ch && k<=ch1){
//                   tot=(long)((long)tot+(long)maxx(1,ind+1,str,k,n))%(long)mod;
//               }
//               else if(k==ch && k<=ch1){
//
//               }
//
//
//
//
//           }
//           return aa[ind][flag]=tot;
//
//       }else{
//           long tot=0;
//           for(int j=1;j<=k;j++){
//               tot=(long)((long)tot+(long)maxx(1,ind+1,str,k,n))%(long)mod;
//           }
//           return aa[ind][flag]=tot;
//       }
//
//
//    }
//static HashSet<String> hashSet;
//    static HashSet<String> hashset;
//    static int maxx(String str,String st,int n,int ind,int k){
//        if(ind>=str.length()){
//            int i=0,j=st.length()-1;
//            int flag=0;
//            while(i<j){
//                if(st.charAt(i)!=st.charAt(j)){
//                    flag=1;break;
//                }
//                i++;j--;
//            }
//            if(flag==0 && str.compareTo(st)>0 ){
//                hashSet.add(st);
//            }
//            return 0;
//        }
//        if(hashset.contains(st)){
//            return 0;
//        }
//        for(int j=0;j<k;j++){
//            char ch=(char)('a'+j);
//            maxx(str,st+String.valueOf(ch),n,ind+1,k);
//        }
//        hashset.add(st);
//        return 0;
//    }
//    static class TreeNode{
//        char ch;
//        TreeNode left,right;
//        TreeNode(char ch){
//            this.ch=ch;
//        }
//    }
//    static void Java(){
//        try{
//            System.out.println("Inside Java");
//            throw new RuntimeException("demo");
//        }
//        finally {
//            System.out.println("Java's finally");
//        }
//    }
//    static void Python(){
//        try{
//            System.out.println("Inside Python");
//            return;
//        }
//        finally {
//            System.out.println("Python's finally");
//        }
//    }
//
////    static long[][] aa;
////    static long mod=(long)((long)Math.pow(10,9)+(long)7);
//    static void postorder(TreeNode root){
//        if(root==null){
//            return;
//        }
//        postorder(root.left);
//        postorder(root.right);
//        System.out.println(root.ch);
//    }
//    static boolean fff=false;
//    static void maxx(List<Integer> lis,int ind,long n){
//        if(ind>=lis.size()){
//            return;
//        }
//        if(n<0){
//            return;
//        }
//        if(n==0){
//            fff=true;
//            return;
//        }
//
//
//
//        maxx(lis,ind+1,n);
//        if(fff){
//            return;
//        }
//        long tt=lis.get(ind);
//        while(true){
//            n=n-tt;
//            if(n<0){
//                break;
//            }
//            for(int i=0;i<lis.size();i++){
//                if(n%lis.get(i)==0){
//                    fff=true;
//                    break;
//                }
//            }
//            maxx(lis,ind,n);
//            if(fff){
//                return;
//            }
//
//        }
//
//    }
//    static class compy implements Comparator<long[]> {
//
//        public int compare(long[] a,long[] b) {
//
//        return Long.compare(a[0],b[0]);
//        }
//
//    }
    static int[] prime;




//    static long maxx(int ind, long arr[], int flag,int k,int tot) {
//        if (ind >= arr.length && tot < k) {
//            return Integer.MIN_VALUE;
//        }
//        if (ind >= arr.length) {
//            return 0;
//        }
//        if(flag==0 && k==tot){
//            return 0;
//        }
//        if (aa[ind][flag][tot] != Integer.MAX_VALUE) {
//            return aa[ind][flag][tot];
//        }
//        if(flag==0){
//            return aa[ind][flag][tot]=Math.max( maxx(ind+1,arr,0,k,tot),maxx(ind+1,arr,1,k,tot+1)+(tot+1)*arr[ind] );
//        }else{
//            return aa[ind][flag][tot]=Math.max( maxx(ind+1,arr,1,k,tot)+tot*arr[ind],maxx(ind,arr,0,k,tot)  );
//        }
//    }
//
//    static long[][][] aa;

//    static int maxx(int ind,int[] arr){
//        if(ind-1<0){
//            return arr[0];
//        }
//        if(aa[ind]!=Integer.MAX_VALUE){
//            return aa[ind];
//        }
//        int min=Integer.MAX_VALUE;
//        min=maxx(ind-1,arr)-arr[ind];
//        min=Math.min( min,maxx(ind-1,arr)+arr[ind] );
//        if(arr[ind]<0){
//
//        }
//        min=Math.min(min,maxx(ind-1,arr)*arr[ind]);
//        return aa[ind]=min;
//    }
//static int[][] aa;
//    static boolean[] vis;
//    static long tot=0;
//    static void maxx(int src,LinkedList<Integer>[] lin){
//        vis[src]=true;
//        tot=(long)(tot+(long)1);
//        for(Integer i:lin[src]){
//            if(vis[i]){
//                continue;
//            }
//            maxx(i,lin);
//        }
////        vis[src]=false;
//    }
//    static int min=Integer.MAX_VALUE;
//    static int maxx(int ind,int[] arr,int sum,int tot){
//        if(ind>=arr.length){
//            int tt=Math.max( tot,sum-tot );
//            min=Math.min(tt,min);
//            return 0;
//        }
//        if(aa[ind][tot]!=-1){
//            return aa[ind][tot];
//        }
//        return aa[ind][tot]=maxx(ind+1,arr,sum,tot+arr[ind])+maxx(ind+1,arr,sum,tot);
//
//    }


    static class com implements Comparator<long[]> {
        public int compare(long[] a, long[] b) {
            return Long.compare(a[0], b[0]);
        }
    }

    static class comm implements Comparator<long[]> {
        public int compare(long[] a, long[] b) {
            return Long.compare(a[1], b[1]);
        }
    }

    static int root(int a, int[] num) {
        while (a != num[a]) {
            num[a] = num[num[a]];
            a = num[a];
        }
        return a;
    }

    static int roott(int a, int num[]) {
        while (a != num[a]) {
            num[a] = num[num[a]];
            a = num[a];
        }
        return a;
    }

    static class compa implements Comparator<int[]> {
        public int compare(int[] a, int[] b) {
            return a[0] - b[0];
        }
    }

    static void maxx(int src, int d, int parent, LinkedList<Integer>[] lin) {
        if (d % 2 == 0) {
            even.add(src);
        } else {
            odd.add(src);
        }
        for (Integer v : lin[src]) {
            if (v != parent) {
                maxx(v, d + 1, src, lin);
            }
        }
    }

    static boolean fff = false;

    static void mmax(String str, int start, int end, int ind) {
        if (start < 0 && end >= str.length()) {
            fff = true;
            return;
        }
        char ch = (char) (ind + 'a');
        if (start >= 0 && str.charAt(start) == ch) {
            mmax(str, start - 1, end, ind + 1);
        }
        if (start == end) {
            return;
        }
        if (end < str.length() && str.charAt(end) == ch) {
            mmax(str, start, end + 1, ind + 1);
        }
    }

    static HashSet<Integer> odd, even;
    static long maxx(int x,int y,int[][] a ,long c,int flag){
        if(aa[x][y][flag]!=-1){
            return aa[x][y][flag];
        }
        if(flag==0){
            long min = Long.MAX_VALUE;
            if (x + 1 < a.length) {
                min = Math.min((long)((long)maxx(x+1,y,a,c,1)+(long)c+(long)a[x][y]), (long)maxx(x + 1, y, a, c,0) );
            }

            if (y + 1 < a[0].length) {
                min = Math.min(min,(long)maxx(x, y + 1, a, c,0) );
                min = Math.min(min,(long)((long)maxx(x,y+1,a,c,1)+(long)c+(long)a[x][y]) );
            }


            return aa[x][y][flag]=min;

        }else {
            long min = (long)a[x][y];
            if (x + 1 < a.length) {
                min = Math.min(min, (long)((long)maxx(x + 1, y, a, c,1) + (long)c));
            }

            if (y + 1 < a[0].length) {
                min = Math.min(min, (long)((long)maxx(x, y + 1, a, c,1) + (long) c) );
            }
            return aa[x][y][flag]=min;
        }


    }
    static long[][][] aa;
    static void dfs(int x,int y){
        int[][] dis=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        for(int j=0;j<dis.length;j++){
            if(valid(dis[j][0]+x,dis[j][1]+y)){
                vis[x+dis[j][0]][y+dis[j][1]]=true;
                dfs(x+dis[j][0],y+dis[j][1]);
            }
        }
    }
    static boolean valid(int x,int y){
        if(x<0 || y<0 || x>=stringBuilders.length || y>=stringBuilders[0].length() || vis[x][y] ){
            return false;
        }
        return true;
    }
    static boolean valid1(int x,int y){
        if(x<0 || y<0 || x>=stringBuilders.length || y>=stringBuilders[0].length() || vis1[x][y]  ){
            return false;
        }
        return true;
    }
    static boolean[][] vis,vis1;
    static HashSet<StringBuilder[]> hashSet;
//    static boolean maxx(int k,int x,int y){
//        if(k==0){
//            vis=new boolean[stringBuilders.length][stringBuilders[0].length()];
//            dfs(x,y);
//            for(int j=0;j<stringBuilders.length;j++){
//                for(int i=0;i<stringBuilders[0].length();i++){
//                    if(stringBuilders[j].charAt(i)=='#' && !vis[j][i] ){
//                        return false;
//                    }
//                }
//            }
//            StringBuilder stringBuilder[]=stringBuilders.clone();
//            hashSet.add(stringBuilder);
//            return true;
//        }
//        if(stringBuilders[x].charAt(y)=='.'){
//            stringBuilders[x].setCharAt(y,'#');
//            int[][] dis=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
//            for(int j=0;j<dis.length;j++){
//                if(valid1(dis[j][0]+x,dis[j][1]+y)){
//                    vis1[x+dis[j][0]][y+dis[j][1]]=true;
//
//                    if(maxx(k-1,x+dis[j][0],y+dis[j][1])){}
//                    vis1[x+dis[j][0]][y+dis[j][1]]=false;
//                }
//            }
//            stringBuilders[x].setCharAt(y,'.');
//            for(int j=0;j<dis.length;j++){
//                if(valid1(dis[j][0]+x,dis[j][1]+y)){
//                    vis1[x+dis[j][0]][y+dis[j][1]]=true;
//
//                    if(maxx(k,x+dis[j][0],y+dis[j][1])){}
//                    vis1[x+dis[j][0]][y+dis[j][1]]=false;
//                }
//            }
//        }else{
//            int[][] dis=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
//            for(int j=0;j<dis.length;j++){
//                if(valid1(dis[j][0]+x,dis[j][1]+y)){
//                    vis1[x+dis[j][0]][y+dis[j][1]]=true;
//
//                    if(maxx(k,x+dis[j][0],y+dis[j][1])){}
//                    vis1[x+dis[j][0]][y+dis[j][1]]=false;
//                }
//            }
//        }
//        return false;
//    }
    public interface Flyer { int j =5;}
    static StringBuilder[] stringBuilders;
    static int k=0;
    static void sieveOfEratosthenes(int n) {
        boolean primes[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            primes[i] = true;

        for (int p = 2; p * p <= n; p++) {
            if (primes[p]) {
                for (int i = p * p; i <= n; i += p) {
                    primes[i] = false;

                }
            }
        }


        for (int i = 2; i <= n; i++) {
            if(primes[i]){
                pr.add(i);
            }
        }
    }

    static long maxx(int ind,int k,long t1,long t2,int flag){
        if(ind==k){
            return 1l;
        }
        if(dpp[ind][flag]!=-1){
            return dpp[ind][flag];
        }
        if(flag==0){
            return  dpp[ind][flag]= (long)((long)((long)maxx(ind+1,k,t1,t2,0)*(long)t1)%(long)mod+(long)((long)maxx(ind+1,k,t1,t2,1)*(long)1)%mod)%mod;
        }else{
            return  dpp[ind][flag]= (long)((long)((long)maxx(ind+1,k,t1,t2,1)*(long)t2)%(long)mod);
        }
    }
    static long maxx(int ind,int k,int flag){
        if(ind==k){
            if(flag==0){
                return 0l;
            }
            return 1l;
        }
        if(dpp[ind][flag]!=-1){
            return dpp[ind][flag];
        }
        if(flag==0) {
            return dpp[ind][flag] = (long) ((long) maxx(ind + 1, k,0) + (long) maxx(ind + 1, k,1)) % mod;
        }else{
            return dpp[ind][flag] = (long) ((long) maxx(ind + 1, k,1)*2l ) % mod;

        }
    }
    static long mod=(long)((long)Math.pow(10,9)+(long)7);
    static List<Integer> pr;
    static long[][] dpp;

    static class comps implements Comparator<int[]> {
        public int compare(int[] a,int[] b){

                return a[0]-b[0];

        }
    }

    public static int maxEvents(int[][] events) {
//        point[] pt=new point[events.length];
        PriorityQueue<Integer> pq=new PriorityQueue<>();

//        for(int j=0;j<pt.length;j++){
//            pt[j]=new point(events[j][0],events[j][1]);
//        }
//        Arrays.sort(pt,new comp());
        // int i=pt[0].start+1;
        // int tot=1;
        // for(int j=1;j<pt.length;j++){
        //     // if(pt[j].start>=i){
        //     //     tot++;
        //     //     i=pt[j].start+1;
        //     // }
        //     if(pt[j].start<=i && pt[j].end>=i){
        //         tot++;i=i+1;
        //     }else if(pt[j].start>i){
        //         i=pt[j].start+1;
        //         tot++;
        //     }
        //    // else if(pt[j].start==i && pt[j].start!=pt[j].end ){
        //    //      tot++;
        //    //      i=pt[j].start+1;
        //    //  }
        // }
        int i=0;
        int tot=0;
        int d=-1;
        while(!pq.isEmpty() || i<events.length ){
            if(pq.isEmpty()){
                d=events[i][0];
            }
            while(i<events.length && events[i][0]<=d ){
                pq.add(events[i][1]);
                i++;
            }
            pq.poll();
            d++;
            tot++;
            while(!pq.isEmpty() && pq.peek()<d){
                pq.poll();
            }
        }
        return tot;
    }

   


    public static void main(String[] args) throws IOException {



        
        Scanner s = new Scanner(System.in);



        int t = s.nextInt();

        for(int j=0;j<t;j++){
          int n = s.nextInt();
          String str=s.next();
          int aa=0;
          int bb=0;
          int tot=0;
          int flag=0;
          HashMap<Integer,Integer> hashMap=new HashMap<>();

          for(int i=0;i<n;i++){
              if(str.charAt(i)=='a'){
                  tot++;
              }else{
                  tot--;
              }
              if(hashMap.get(tot-1)!=null){
                  flag=1;
                  i=i+1;
                  System.out.println(hashMap.get(tot-1)+" "+i);
                  break;
              }
              hashMap.put(tot,i+1);
          }
          if(flag==0){
              if(tot==0){
                  System.out.println(1+" "+n);
              }else{
                  System.out.println(-1+" "+-1);
              }
          }else{

          }

        }





       // int t = s.nextInt();

        //for (int j = 0; j < t; j++) {
//            long n = s.nextLong();
//            long a1=(long)((long)((long)n/(long)6)*(long)15);
//            long a2=(long)((long)((long)n/(long)8)*(long)20);
//            long a3=(long)((long)((long)n/(long)10)*(long)25);
//            if((long)((long)n%8l)<=6l && (long)((long)n%8l)!=0){
//                a2=(long)((long)a2+(long)15);
//            }else if( (long)((long)n%8l) != 0 ){
//                a2=(long)((long)a2+(long)20);
//            }
//
//            if((long)((long)n%10l)<=6l && (long)((long)n%10l)!=0){
//                a3=(long)((long)a3+(long)15);
//            }
//            else if((long)((long)n%10l)<=8l && (long)((long)n%10l)!=0){
//                a3=(long)((long)a3+(long)20);
//            }
//            else if( (long)((long)n%10l)!=0 ){
//                a3=(long)((long)a3+(long)25);
//            }
//
//            if((long)((long)n%6l) != 0){
//                a1=(long)((long)a1+(long)15);
//            }
//
//            System.out.println(Math.min(a1,Math.min(a3,a2)));
//            System.out.println(a1);
//            System.out.println(a2);
//            System.out.println(a3);
//            int n=s.nextInt();
//            int[][] num=new int[n][2];
//            for(int i=0;i<n;i++){
//                num[i][0]=s.nextInt();
//            }
//            for(int i=0;i<n;i++){
//                num[i][1]=s.nextInt();
//            }
//            dp=new long[n][2][2];
//            for(int i=0;i<n;i++){
//                for(int k=0;k<2;k++){
//                    Arrays.fill(dp[i][k],-1);
//                }
//            }
//            System.out.println(maxx(0,0,0,num));

        //}

    }
    static long[][][] dp;
    static long maxx(int x,int y,int y1,int[][] num){
        int x1=x+y-y1;
        if(x1==num.length-1 && y1==num[0].length-1){
            return 0;
        }
//        if(dp[x][y][y1] != -1){
//            return dp[x][y][y1];
//        }
        long res=0;
        if(x1 != x){
            res=num[x1][y1];
        }
        long max=Integer.MAX_VALUE;
        if(x+1<num.length && y1+1<num[0].length){
            max=maxx(x+1,y,y1+1,num);
        }
        if(x+1<num.length && x1+1<num.length){
            max=Math.min(max,maxx(x+1,y,y1,num));
        }
        if(y+1<num[0].length && x1+1<num.length){
            max=Math.min(max,maxx(x,y+1,y1,num));
        }
        if(y+1<num[0].length && y1+1<num[0].length){
            max=Math.min(max,maxx(x,y+1,y1+1,num));
        }
        if(max==Integer.MAX_VALUE){
            return dp[x][y][y1]=res;
        }
        return dp[x][y][y1]=max+res;


    }










    //
//        ArrayList obj = new ArrayList(); obj.add("A"); obj.add("B"); obj.add("C"); obj.add(1, "D"); System.out.println(obj); }
//        for(int i=2;i<5;i++) { for(int j=2;j<5; j+=3) { System.out.println((k+=3) *(++i)); } }
//        while(i<10 && i >24){
//            System.out.println("aa");
//        }
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        String stt = br.readLine().trim();
//        int t = Integer.parseInt(stt);
//        int q = Integer.parseInt(stt[1]);
//          Scanner s=new Scanner(System.in);
//        Scanner scanner=new Scanner(System.in);
//        int n=scanner.nextInt();
//        int k= scanner.nextInt();
//       stringBuilders=new StringBuilder[n];
//
//        for(int j=0;j<n;j++){
//            stringBuilders[j]=new StringBuilder(scanner.next());
//        }
//        vis1=new boolean[stringBuilders.length][n];
//        hashSet=new HashSet<>();maxx(k,0,0);
//        System.out.println(hashSet.size());

//        HashMap<Integer,HashMap<Integer,List<Integer>>> hashMap=new HashMap<>();
//        for(int j=0;j<n;j++){
//            hashMap.put(j,new HashMap<>());
//            for(int i=0;i<n;i++){
//                hashMap.get(j).putIfAbsent(aa[j][i],new ArrayList<>());
//                hashMap.get(j).get(aa[j][i]).add(i);
//            }
//        }
//        List<Integer> ans=new ArrayList<>();
//        for(Integer i:hashMap.get(0).keySet()){
//            HashSet<Integer> hashSet=new HashSet<>();
//            int jaa=hashMap.get(0).get(i).get(0);
//            hashSet.add(jaa);
//            hashMap.get(0).get(i).remove(new Integer(jaa));
//            int flag=0;
//
//            for(int j=1;j<n;j++){
//                if(hashMap.get(j).get(i)!=null) {
//                    List<Integer> list=hashMap.get(j).get(i);
//                    int flag1=0;
//                    for (int k = 0; k < list.size(); k++) {
//                        int kk=list.get(k);
//                        if(!hashSet.contains(kk)){
//                            hashSet.add(kk);
//                            list.remove(new Integer(kk));
//                            flag1=1;
//                            break;
//                        }
//                    }
//                    if(flag1==0){
//                        flag=1;break;
//                    }
//                }else{
//                    flag=1;
//                    break;
//                }
//            }
//            if(flag==0){
//                ans.add(i);
//            }
//        }
//        Reader scanner=new Reader();
//        int t= scanner.nextInt();
//        for(int j=0;j<t;j++){
//            int n= scanner.nextInt();
//            int[] arr=new int[n];
//            HashSet<Integer> hashSet=new HashSet<>();
//            HashMap<Integer, Integer> hashMap=new HashMap<>();
//            int flag=0;
//            for(int i=0;i<n;i++){
//                arr[i]=scanner.nextInt();
//                if(hashSet.contains(arr[i])){
//                    flag=1;
//                }
//                hashSet.add(arr[i]);
//            }
//            if(flag==1){
//                System.out.println("YES");
//            }else {
//                SS:
//                for (int i = 0; i < n; i++) {
//                    for (int k = 0; k < n; k++) {
//                        if(hashSet.contains(arr[i]-arr[k]) || hashSet.contains(arr[k]-arr[i]) )
//                        {
//                            flag=1;break SS;
//                        }
//                    }
//                }
//                if(flag==1){
//                    System.out.println("YES");
//                }else{
//                    List<Integer> list=new ArrayList<>();
//                    for(int i=0;i<n;i++){
//                        for(int k=i+1;k<n;k++){
//                            list.add(arr[k]+arr[i]);
//                        }
//                    }
//                    flag=0;
//                    for(int i=0;i<list.size();i++){
//                        HashSet<Integer> hashSet1=new HashSet<>();
//                        for(int k=0;k<n;k++){
//                            if(hashSet.contains(list.get(i)-arr[k])  ){
//                                hashSet1.add(list.get(i)-arr[k]);
//                            }
//                            if(hashSet.contains(arr[k]-list.get(i))){
//                                hashSet1.add(-list.get(i)+arr[k]);
//                            }
//                        }
//                        if(hashSet1.size()>=3){
//                            flag=1;
//                            break;
//                        }
//                    }
//                    if(flag==1){
//                        System.out.println("YES");
//                    }else {
//                        list=new ArrayList<>();
//                        for(int i=0;i<n;i++){
//                            for(int k=i+1;k<n;k++){
//                                for(int l=k+1;l<n;l++) {
//                                    list.add(arr[k] + arr[i]+arr[l]);
//                                }
//                            }
//                        }
//                        flag=0;
//                        for(int i=0;i<list.size();i++){
//
//                            HashSet<Integer> hashSet1=new HashSet<>();
//                            for(int k=0;k<n;k++){
//                                if(hashSet.contains(list.get(i)-arr[k])  ){
//                                    hashSet1.add(list.get(i)-arr[k]);
//                                }
//                                if(hashSet.contains(arr[k]-list.get(i))){
//                                    hashSet1.add(-list.get(i)+arr[k]);
//                                }
//                            }
//                            if(hashSet1.size()>=4){
//                                flag=1;
//                                break;
//                            }
//                        }
//                        if(flag==1){
//                            System.out.println("YES");
//                        }else {
//                            System.out.println("NO");
//                        }
//                    }
//                }
//            }
//
//        }




//int n= scanner.nextInt();
//int m=scanner.nextInt();
//LinkedList<Integer>[] linkedLists=new LinkedList[n+1];
//for(int j=1;j<=n;j++){
//    linkedLists[j]=new LinkedList<>();
//}
//for(int j=0;j<m;j++){
//    int u= scanner.nextInt();
//    int v= scanner.nextInt();
//    linkedLists[u].add(v);
//    linkedLists[v].add(u);
//}
//Queue<Integer> queue=new LinkedList<>();
//queue.add(1);
//int[] vis=new int[n+1];
//Arrays.fill(vis,Integer.MAX_VALUE);
//vis[1]=0;
//long[] paths=new long[n+1];
//boolean[] viss=new boolean[n+1];
//viss[1]=true;
//paths[1]=1;
//
//while (!queue.isEmpty()){
//    int te=queue.poll();
//
//
//    for(Integer v:linkedLists[te]){
//        if(!viss[v]){
//            viss[v]=true;
//            queue.add(v);
//        }
//        if(vis[te]+1<vis[v]){
//            vis[v]=vis[te]+1;
//            paths[v]=paths[te];
//        }else if(vis[v]==vis[te]+1){
//            paths[v]=(long)((long)((long)paths[v]+(long)paths[te])%mod);
//        }
//
//    }
//}
//        System.out.println(paths[n]);




//    static long maxx(int ind,int ind1,String str,String s){
//        if(ind>=s.length()){
//            return 1l;
//        }
//        if(ind1>=str.length()){
//            return 0l;
//        }
//        if(dp[ind][ind1]!=-1){
//            return dp[ind][ind1];
//        }
//        if(str.charAt(ind1)==s.charAt(ind)){
//           // list.add(ind1);
//            dp[ind][ind1]=(long)((long)maxx(ind+1,ind1+1,str,s) )%(long)mod;
//            //list.remove(list.size()-1);
//            dp[ind][ind1]=(long)((long)dp[ind][ind1]+(long)maxx(ind,ind1+1,str,s) )%(long)mod;
//            return dp[ind][ind1];
//        }else{
//            return dp[ind][ind1]=(long)(maxx(ind,ind1+1,str,s) )%(long)(mod);
//        }
//    }
//    static long[][] dp;
//    static long mod=(long)(Math.pow(10,9)+(long)7);
//
//    static class compp implements Comparator<int[]>{
//        public int compare(int[] a,int[] b){
//            return a[0]-b[0];
//        }
//    }
//    static int[][][] dp;
//    static int maxx(int ind,int tot,int tot1,String str){
//        if(ind>=str.length()){
//            return 0;
//        }
//        if(dp[ind][tot][tot1]!=-1){
//            return dp[ind][tot][tot1];
//        }
//        if(ind%2==0){
//            int t=0;
//            int t1=0;
//            for(int i=ind;i<str.length();i++){
//                if(i%2==0 ){
//                    t++;
//                }else {
//                    t1++;
//                }
//            }
//            if(t+tot<tot1){
//                return dp[ind][tot][tot1]=0;
//            }
//            if(t1+tot1<tot){
//                return dp[ind][tot][tot1]=0;
//            }
//            if(str.charAt(ind)=='0'){
//                return dp[ind][tot][tot1]=maxx(ind+1,tot,tot1,str)+1;
//            }else if(str.charAt(ind)=='1'){
//                return dp[ind][tot][tot1]=maxx(ind+1,tot+1,tot1,str)+1;
//            }else{
//                return dp[ind][tot][tot1]=Math.min(maxx(ind+1,tot,tot1,str)+1,maxx(ind+1,tot+1,tot1,str)+1);
//            }
//        }else{
//            int t=0;
//            int t1=0;
//            for(int i=ind;i<str.length();i++){
//                if(i%2==0 ){
//                    t++;
//                }else {
//                    t1++;
//                }
//            }
//            if(t+tot<tot1){
//                return dp[ind][tot][tot1]=0;
//            }
//            if(t1+tot1<tot){
//                return dp[ind][tot][tot1]=0;
//            }
//            if(str.charAt(ind)=='0'){
//                return dp[ind][tot][tot1]=maxx(ind+1,tot,tot1,str)+1;
//            }else if(str.charAt(ind)=='1'){
//                return dp[ind][tot][tot1]=maxx(ind+1,tot,tot1+1,str)+1;
//            }else{
//                return dp[ind][tot][tot1]=Math.min(maxx(ind+1,tot,tot1+1,str)+1,maxx(ind+1,tot,tot1,str)+1);
//            }
//        }
//    }
    static boolean ffa=false;
//    static int maxx(int ind1,int ind2,int flag,String str,String t1){
//        if(ind2>=t1.length()){
//            ffa=true;
//            return 1;
//        }
//        if(ind1<0 || ind1>=str.length()){
//            return -1;
//        }
//        if(aaa[ind1][ind2][flag]!=0){
//            return aaa[ind1][ind2][flag];
//        }
//        if( flag==0 && str.charAt(ind1)==t1.charAt(ind2) ){
//            return aaa[ind1][ind2][flag]= Math.max( maxx(ind1+1,ind2+1,0,str,t1),maxx(ind1+1,ind2,0,str,t1) );
//        }else if(flag==0 ){
//            return aaa[ind1][ind2][flag]=Math.max( maxx(ind1+1,ind2,0,str,t1),maxx(ind1-1,ind2,1,str,t1) );
//        }else if(flag==1) {
//            return aaa[ind1][ind2][flag]=Math.max( maxx(),maxx() );
//        }
//    }
    static int[][][] aaa;
    static class comp2 implements Comparator<long[]>{
        @Override
        public int compare(long[] o1, long[] o2) {
            return Long.compare(o2[2],o1[2]);
        }
    }


}











