After a long party Petya decided to return home, but he turned out to be at the opposite end of the town from his home. There are n crossroads in the line in the town, and there is either the bus or the tram station at each crossroad.

The crossroads are represented as a string s of length n, where s_i = A, if there is a bus station at i-th crossroad, and s_i = B, if there is a tram station at i-th crossroad. Currently Petya is at the first crossroad (which corresponds to s_1) and his goal is to get to the last crossroad (which corresponds to s_n).

If for two crossroads i and j for all crossroads i, i+1, …, j-1 there is a bus station, one can pay a roubles for the bus ticket, and go from i-th crossroad to the j-th crossroad by the bus (it is not necessary to have a bus station at the j-th crossroad). Formally, paying a roubles Petya can go from i to j if s_t = A for all i ≤ t < j. 

If for two crossroads i and j for all crossroads i, i+1, …, j-1 there is a tram station, one can pay b roubles for the tram ticket, and go from i-th crossroad to the j-th crossroad by the tram (it is not necessary to have a tram station at the j-th crossroad). Formally, paying b roubles Petya can go from i to j if s_t = B for all i ≤ t < j.

For example, if s="AABBBAB", a=4 and b=3 then Petya needs:

<image>

  * buy one bus ticket to get from 1 to 3, 
  * buy one tram ticket to get from 3 to 6, 
  * buy one bus ticket to get from 6 to 7. 



Thus, in total he needs to spend 4+3+4=11 roubles. Please note that the type of the stop at the last crossroad (i.e. the character s_n) does not affect the final expense.

Now Petya is at the first crossroad, and he wants to get to the n-th crossroad. After the party he has left with p roubles. He's decided to go to some station on foot, and then go to home using only public transport.

Help him to choose the closest crossroad i to go on foot the first, so he has enough money to get from the i-th crossroad to the n-th, using only tram and bus tickets.

Input

Each test contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10^4).

The first line of each test case consists of three integers a, b, p (1 ≤ a, b, p ≤ 10^5) — the cost of bus ticket, the cost of tram ticket and the amount of money Petya has.

The second line of each test case consists of one string s, where s_i = A, if there is a bus station at i-th crossroad, and s_i = B, if there is a tram station at i-th crossroad (2 ≤ |s| ≤ 10^5).

It is guaranteed, that the sum of the length of strings s by all test cases in one test doesn't exceed 10^5.

Output

For each test case print one number — the minimal index i of a crossroad Petya should go on foot. The rest of the path (i.e. from i to n he should use public transport).

Example

Input


5
2 2 1
BB
1 1 1
AB
3 2 8
AABBBBAABB
5 3 4
BBBBB
2 1 1
ABABAB


Output


2
1
3
1
6
import java.io.*;
import java.util.*;

public class Stack2 {

    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')
                    break;
                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 Reader sc = new Reader();
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        /*
         * For integer input: int n=inputInt();
         * For long input: long n=inputLong();
         * For double input: double n=inputDouble();
         * For String input: String s=inputString();
         * Logic goes here
         * For printing without space: print(a+""); where a is a variable of any datatype
         * For printing with space: printSp(a+""); where a is a variable of any datatype
         * For printing with new line: println(a+""); where a is a variable of any datatype
         */
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
       procee: for (int i = 0; i < t; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int p=sc.nextInt();
            String s=sc.next();
            List<Integer> list=new ArrayList<>();
            list.add(0);
            StringBuilder stringBuilder=new StringBuilder();
            char prev=s.charAt(0);
            stringBuilder.append(prev);
            for(int j=1;j<s.length()-1;j++){
                char ch=s.charAt(j);
                if(ch!=prev){
                    stringBuilder.append(ch);
                    list.add(j);
                }
                prev=ch;
            }

            long[] psum=new long[stringBuilder.length()];
            long sum=0;
            for(int j=stringBuilder.length()-1;j>=0;j--){
                if(stringBuilder.charAt(j)=='B'){
                    sum+=b;
                }else {
                    sum+=a;
                }
                psum[j]=sum;
            }
            for(int j=0;j<=stringBuilder.length()-1;j++){
               if(psum[j]<=p){
                  int ans= list.get(j)+1;
                   System.out.println(ans);
                   continue procee;
               }
            }
            System.out.println(s.length());


        }

        bw.flush();
        bw.close();


    }

    public static void bfs(int r, int c, Queue<int[]> queue, long[][] dis, char[][] map, boolean[][] visited) {
        while (!queue.isEmpty()) {
            int[] ar = queue.poll();
            int x = ar[0];
            int y = ar[1];
            if (x + 1 < r) {
                if (map[x + 1][y] != 'T' && dis[x + 1][y] > (dis[x][y] + 1)) {
                    dis[x + 1][y] = Math.min(dis[x + 1][y], (dis[x][y] + 1));
                    queue.add(new int[]{x + 1, y});
                } /*else if (map[x][y] != map[x + 1][y] && dis[x + 1][y] > (dis[x][y] + 1)) {
                    dis[x + 1][y] = Math.min(dis[x + 1][y], dis[x][y] + 1);
                    queue.add(new int[]{x + 1, y});
                }*/
              /*  if(!visited[x+1][y] ){
                    queue.add(new int[]{x + 1, y});
                    visited[x+1][y]=true;
                }*/


            }
            if (y + 1 < c) {
                if (map[x][y + 1] != 'T' && dis[x][y + 1] > (dis[x][y] + 1)) {
                    dis[x][y + 1] = Math.min(dis[x][y + 1], dis[x][y] + 1);
                    queue.add(new int[]{x, y + 1});
                } /*else if (map[x][y] != map[x][y + 1] && dis[x][y + 1] > (dis[x][y] + 1)) {
                    dis[x][y + 1] = Math.min(dis[x][y + 1], dis[x][y] + 1);
                    queue.add(new int[]{x, y + 1});
                }*/
               /* if( !visited[x][y+1]){
                    queue.add(new int[]{x, y+1});
                    visited[x][y+1]=true;
                }*/


            }
            if (x - 1 >= 0) {
                if (map[x - 1][y] != 'T' && dis[x - 1][y] > (dis[x][y] + 1)) {
                    dis[x - 1][y] = Math.min(dis[x - 1][y], (dis[x][y] + 1));
                    queue.add(new int[]{x - 1, y});
                } /*else if (map[x][y] != map[x - 1][y] && dis[x - 1][y] > (dis[x][y] + 1)) {
                    dis[x - 1][y] = Math.min(dis[x - 1][y], dis[x][y] + 1);
                    queue.add(new int[]{x - 1, y});
                }*/
               /* if(!visited[x-1][y]){
                    queue.add(new int[]{x - 1, y});
                    visited[x-1][y]=true;
                }*/


            }
            if (y - 1 >= 0) {
                if (map[x][y - 1] != 'T' && dis[x][y - 1] > (dis[x][y] + 1)) {
                    dis[x][y - 1] = Math.min(dis[x][y - 1], (dis[x][y] + 1));
                    queue.add(new int[]{x, y - 1});
                } /*else if (map[x][y] != map[x][y - 1] && dis[x][y - 1] > (dis[x][y] + 1)) {
                    dis[x][y - 1] = Math.min(dis[x][y - 1], dis[x][y] + 1);
                    queue.add(new int[]{x, y - 1});
                }*/
               /* if(!visited[x][y-1]){
                    queue.add(new int[]{x , y-1});
                    visited[x][y-1]=true;
                }*/


            }
        }
    }


    public static void dfs1(List<List<Integer>> g, boolean[] visited, Stack<Integer> stack, int num) {
        visited[num] = true;
        for (Integer integer : g.get(num)) {
            if (!visited[integer]) {
                dfs1(g, visited, stack, integer);
            }
        }
        stack.push(num);
    }

    public static void dfs2(List<List<Integer>> g, boolean[] visited, List<Integer> list, int num, int c, int[] raj) {
        visited[num] = true;

        for (Integer integer : g.get(num)) {
            if (!visited[integer]) {
                dfs2(g, visited, list, integer, c, raj);
            }
        }
        raj[num] = c;
        list.add(num);

    }

    public static int inputInt() throws IOException {
        return sc.nextInt();
    }

    public static long inputLong() throws IOException {
        return sc.nextLong();
    }

    public static double inputDouble() throws IOException {
        return sc.nextDouble();
    }

    public static String inputString() throws IOException {
        return sc.readLine();
    }

    public static void print(String a) throws IOException {
        bw.write(a);
    }

    public static void printSp(String a) throws IOException {
        bw.write(a + " ");
    }

    public static void println(String a) throws IOException {
        bw.write(a + "\n");
    }


    public static long getAns(int[] ar, int c, long[][] dp, int i, int sign) {
        if (i < 0) {
            return 1;
        }

        if (c <= 0) {
            return 1;
        }

        dp[i][c] = Math.max(dp[i][c], Math.max(ar[i] * getAns(ar, c - 1, dp, i - 1, sign), getAns(ar, c, dp, i - 1, 1)));
        return dp[i][c];
    }


    public static long power(long a, long b, long c) {
        long ans = 1;
        while (b != 0) {
            if (b % 2 == 1) {
                ans = ans * a;
                ans %= c;
            }
            a = a * a;
            a %= c;
            b /= 2;
        }
        return ans;
    }

    public static long power1(long a, long b, long c) {
        long ans = 1;
        while (b != 0) {
            if (b % 2 == 1) {
                ans = multiply(ans, a, c);
            }
            a = multiply(a, a, c);
            b /= 2;

        }
        return ans;

    }

    public static long multiply(long a, long b, long c) {
        long res = 0;
        a %= c;
        while (b > 0) {
            if (b % 2 == 1) {
                res = (res + a) % c;
            }
            a = (a + a) % c;
            b /= 2;
        }

        return res % c;

    }

    public static long totient(long n) {
        long result = n;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                //sum=sum+2*i;
                while (n % i == 0) {
                    n /= i;
                    // sum=sum+n;
                }
                result -= result / i;

            }
        }
        if (n > 1) {
            result -= result / n;

        }
        return result;
    }


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

    public static boolean[] primes(int n) {
        boolean[] p = new boolean[n + 1];
        p[0] = false;
        p[1] = false;
        for (int i = 2; i <= n; i++) {
            p[i] = true;
        }

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

        }
        return p;
    }

}