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 Practice
{
//	static final long mod=7420738134811L;
	static int mod=1000000007;
	static FastReader sc=new FastReader(System.in);
//	static Reader sc=new Reader();
	static  PrintWriter out=new PrintWriter(System.out);
	static int precalc[];
	public static void main(String[] args) throws IOException, FileNotFoundException
	{
//		System.setIn(new FileInputStream("input.txt"));
//		System.setOut(new PrintStream("output.txt"));
		int t=1;
		t=sc.nextInt();
//		StringBuilder sb=new StringBuilder();
		while(t-->0)
		{
			solve();
//			sb.append("\n");
		}
//		out.print(sb);
		out.close();
		out.flush();
	}
	static class Pair implements Cloneable
	{
		int x,y;
		Pair(int a,int b)
		{
			this.x=a;
			this.y=b;
		}
		@Override
		public String toString() 
		{
			return "("+x+" at "+(y+1)+")";
		}
		@Override
		protected Pair clone() throws CloneNotSupportedException {
			return new Pair(this.x,this.y);
		}
	}
	static void arraySort(int arr[])
	{
		ArrayList<Integer> a=new ArrayList<Integer>();
		for (int i = 0; i < arr.length; i++) {
			a.add(arr[i]);
		}
		Collections.sort(a);
		for (int i = 0; i < arr.length; i++) {
			arr[i]=a.get(i);
		}
	}
	static void solve() throws IOException
	{
		int n=sc.nextInt();
		String str=sc.next();
		for(int i=0;i<str.length()-1;i++)
		{
			if(str.charAt(i)!=str.charAt(i+1))
			{
				out.println((i+1)+" "+(i+2));
				return;
			}
		}
		out.println("-1 -1");
	}
	static void print(int arr[][])
	{
		for(int i=0;i<=5;i++)
		{
			for(int j=0;j<=5;j++)
				out.print(arr[i][j]+" ");
			out.println();
		}
		out.println();
	}
	static void ConvertToSum(int arr[][])
	{
		for(int i=1;i<=100;i++)
		{
			for(int j=0;j<=100;j++)
			{
				arr[i][j]=arr[i][j]+arr[i-1][j];
			}
		}
		for(int j=1;j<=100;j++)
		{
			for(int i=0;i<=100;i++)
			{
				arr[i][j]=arr[i][j]+arr[i][j-1];
			}
		}
	}
	static boolean check(long x)
	{
		int start=1,end=1000;
		while(start<=end)
		{
			int mid=(start+end)>>1;
			if(mid*mid*mid==x)
				return true;
			else if(mid*mid*mid<x)
				start=mid+1;
			else
				end=mid-1;
		}
		return false;
	}
	static double dis(Pair circle,int x,int y)
	{
		double dis=Math.abs(circle.x-x)*Math.abs(circle.x-x)+y*y;
		dis=Math.sqrt(dis);
		return dis;
	}
	static int findXOR(int x)	//from 0 to x
	{
		if(x<0)
			return 0;
		if(x%4==0)
			return x;
		if(x%4==1)
			return 1;
		if(x%4==2)
			return x+1;
		return 0;
	}
	static boolean isPrime(long x)
	{
		if(x==1)
			return false;
		if(x<=3)
			return true;
		if(x%2==0 || x%3==0)
			return false;
		for(int i=5;i<=Math.sqrt(x);i+=2)
			if(x%i==0)
				return false;
		return true;
	}
	static double dfs(Node ver,Node par)
	{
		if(ver.adj.size()==1 && ver.adj.get(0)==par)
		{
			return 0;
		}
		else
		{
			double sum=0,c=0;			
			for(Node child: ver.adj)
			if(child!=par)
			{
				c++;
				sum+=dfs(child, ver);
			}
			return 1+(sum/c);
		}
	}
	static boolean LOWER_BOUND(int arr[],int x)
	{
		int low=0,high=arr.length;
		while(low<=high)
		{
			int mid=(low+high)/2;
			if(arr[mid]==x)
			{
				return true;
			}
			else if(arr[mid]<x)
			{
				low=mid+1;
			}
			else
				high=mid-1;
		}
		return false;
	}
	static long gcd(long a,long b)
	{
		return (b==0)?a:gcd(b,a%b);
	}
	static class UnionFind
	{
		  private int size;
		  private int[] sz;
		  private int[] parent;
		  private int numComponents;
		  public UnionFind(int size) 
		  {
		    if (size <= 0) throw new IllegalArgumentException("Size <= 0 is not allowed");
		    this.size = numComponents = size;
		    sz = new int[size];
		    parent = new int[size];
		    for (int i = 0; i < size; i++) 
		    {
		      parent[i] = i; 									// Link to itself (self root)
		      sz[i] = 1;								// Each component is originally of size one
		    }
		  }
		  public int find(int p) 
		  {
		    int root = p;
		    while (root != parent[root])
		    	root = parent[root];
		    while (p != root)
		    {
		      int next = parent[p];
		      parent[p] = root;
		      p = next;
		    }
		    return root;
		  }
		  public void makeParent(int p,int u)
		  {
			  parent[p]=u;
		  }
		  public boolean isConnected(int p, int q) 
		  {
		    return find(p) == find(q);
		  }
		  public int componentSize(int x) 
		  {
		    return sz[find(x)];
		  }
		  public int size() 
		  {
		    return size;
		  }
		  public int components() 
		  {
		    return numComponents;
		  }
		  public void unify(int p, int q) 
		  {
		    int root1 = find(p);
		    int root2 = find(q);
		    if(root1==root2)
		    {
		    	return;
		    }
		    else if (sz[root1] < sz[root2]) 
		    {
		    	parent[root1] = root2;
		    	sz[root2] += sz[root1];
		    	sz[root1] = 0;
		  } 
		    else 
		    {
		    	parent[root2] = root1;
		    	sz[root1] += sz[root2];
		    	sz[root2] = 0;
		    }
		    numComponents--;
		  }
		  void calc()
		  {
			  for(int i=0;i<size;i++)
				  find(i);
			  
		  }
	}
	static class Node
	{
		int vertex;
		ArrayList<Node> adj;
		boolean rec;
		boolean vis;
		int color;
		Node(int v)
		{
			vertex=v;
			adj=new ArrayList<Node>();
			vis=false;
			color=-1;
		}
		@Override
		public String toString() 
		{
			return vertex+" ";
		}
	}
	static class Edge
	{
		Node a;
		Node b;
		Edge(Node m,Node n)
		{
			this.a=m;
			this.b=n;
		}
		@Override
		public String toString() {
			return a.vertex+" "+b.vertex;
		}
	}
	static long power(long x, long y)
	  {
	    long res = 1; 
	    x = x % mod; 
	    if (x == 0)
	      return 0; 
	    while (y > 0)
	    {
	    	if ((y & 1) != 0)
	    		res = (res * x) % mod;
	    	
	    	y = y >> 1; // y = y/2
	    	x = (x * x) % mod;
	    }
	    return res;
	  }
	static long binomialCoeff(long n, long k)
    {
        long res = 1;
        if(k>n)
        	return 0;
        // Since C(n, k) = C(n, n-k)
        if (k > n - k)
            k = n - k;
 
        // Calculate value of
        // [n * (n-1) *---* (n-k+1)] / [k * (k-1) *----* 1]
        for (long i = 0; i < k; ++i) {
            res *= (n - i);
            res /= (i + 1);
        }
 
        return res;
    }
	static class FastReader
	{
        byte[] buf = new byte[2048];
        int index, total;
        InputStream in;
 
        FastReader(InputStream is) 
        {
            in = is;
        }
 
        int scan() throws IOException 
        {
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0) {
                    return -1;
                }
            }
            return buf[index++];
        }
 
        String next() throws IOException 
        {
            int c;
            for (c = scan(); c <= 32; c = scan());
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }
 
        int nextInt() throws IOException 
        {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan());
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
 
        long nextLong() throws IOException 
        {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan());
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
    }
	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();
        }
        public void printarray(int arr[])
        {
        	for (int i = 0; i < arr.length; i++)
				System.out.print(arr[i]+" ");
        	System.out.println();
        }
    }
}








