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 CodingLegacy {

    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Palindrome solver = new Palindrome();

        int t = in.nextInt();

        for (int i = 0; i < t; i++) {
            solver.solve(i + 1, in, out);
        }
        out.close();
    }

    static class Palindrome {
        static long mod = 1000000007;
        static long maxx = (long) 1e18;

        void solve(int testNumber, InputReader in, PrintWriter out) {
            int a = in.nextInt(),b = in.nextInt(),p = in.nextInt();
            char[] s = in.next().toCharArray();
            int n = s.length;
            long sum = 0;
            char pp = s[n-2];
            if(pp == 'A') {
                if(p >= a) {
                    sum = a;
                    p-=a;
                } else {
                    out.println(n);
                    return;
                }
            } else if(pp == 'B') {
                if(p >= b) {
                    sum = b;
                    p-=b;
                } else {
                    out.println(n);
                    return;
                }
            }
            for(int i = n-3;i>=0;i--) {
                if(pp != s[i]) {
                    if(s[i] == 'A') {
                        if(p >= a) {
                            sum += a;
                            p-=a;
                        } else {
                            out.println(i+2);
                            return;
                        }
                        pp = 'A';
                    } else if(s[i] == 'B') {
                        if(p >= b) {
                            p-=b;
                        } else {
                            out.println(i+2);
                            return;
                        }
                        pp = 'B';
                    }
                }
            }
            out.println(1);

        }
    }

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

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

        public static long factorial(int n) {
            long fact = 1;
            for (int i = 1; i <= n; i++) {
                fact *= i;
            }
            return fact;
        }
    }

    static class Characters {
        public static boolean isVovel(char a) {
            return a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u';
        }
    }

    static class Binary {
        public static long numberOfBits(long n) {
            long count = 0;
            while (n > 0) {
                count++;
                n >>= 1;
            }
            return count;
        }

        public static long numberOfSetBits(long n) {
            long count = 0;
            int p = 1;
            while (n > 0) {
                if ((n & p) == 1) {
                    count++;
                }
                n >>= 1;
            }
            return count;
        }
    }

    static class InputReader {
        BufferedReader reader;
        StringTokenizer tokenizer;

        InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        public Long nextLong() {
            return Long.parseLong(next());
        }
    }
}