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.Arrays;
import java.util.InputMismatchException;
/* * */

public class _c1315_B implements Runnable{
    public static void main(String[] args) {
	    new Thread(null, new _c1315_B(),"Main",1<<27).start();
    }
    @Override
    public void run() {
        FastReader fd = new FastReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int t = fd.nextInt();
        for(int te = 0; te < t; te++){
            int a = fd.nextInt();
            int b = fd.nextInt();
            int cur = fd.nextInt();
            String data = fd.next();

            int i, ans = 1;
            for(i = data.length()-1; i > 0; ){
                char prev = data.charAt(i-1);
                int remove = 0;
                if(prev == 'A'){
                    if(cur < a){
                        ans = i+1;
                        break;
                    }
                    remove = a;
                }
                else{
                    if(cur < b){
                        ans = i+1;
                        break;
                    }
                    remove = b;
                }
                while(i > 0 && data.charAt(i-1) == prev){i--;}
                cur -= remove;
            }
            out.println(ans);

        }
        out.close();
    }

    //Helper functions
    static void getArray(int[] data, boolean isSorted, FastReader fd){
        for(int i = 0; i < data.length; i++){ data[i] = fd.nextInt(); }
        if(isSorted) Arrays.sort(data);
    }
    static int gcd(int a, int b) {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    static int lcm(int a, int b) {
        return (a*b)/gcd(a, b);
    }

    static boolean checkDistinct(int next){// check all digits are distinct.

        String process = String.valueOf(next);
        for(int i = 0;i < process.length()-1; i++){
            String character = String.valueOf(process.charAt(i));
            if(process.substring(i+1).contains(character)){ return false; }
        }
        return true;
    }

    static int limit = (int) 1e7 + 1;
    static int[] facts = new int[limit];
    static void sieve() {  // Store the minimum prime factors of 1 to LIMIT
        facts[1] = 1;
        for (int i = 2; i < limit; i++) {
            if (i % 2 == 0 && i > 2) {
                facts[i] = 2;
            } else {
                facts[i] = i;
            }
        }
        for (int i = 3; i * i < limit; i++) {
            if (facts[i] == i) {
                for (int j = i * i; j < limit; j += i)
                    if (facts[j] == j)
                        facts[j] = i;
            }
        }
    }
    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars==-1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                }
                catch (IOException e) {
                    throw new InputMismatchException();
                }

                if(numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() {
            int c = read();

            while(isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if(c<'0'||c>'9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}
