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
/**
 * ******* Created  on 23/2/20 9:51 PM*******
 */

import java.io.*;
import java.util.*;

public class B1315 implements Runnable {

    private static final int MAX = (int) (1E5 + 5);
    private static final int MOD = (int) (1E9 + 7);
    private static final long Inf = (long) (1E14 + 10);

    private void solve() throws IOException {
        int t = reader.nextInt();;
        while(t-- >0){
            int a = reader.nextInt();
            int b = reader.nextInt();
            int p = reader.nextInt();
            String s = reader.next();
            int n = s.length();
            int i=n-2;int ans =n-1;
            for(;i>=0;){
                int j =i-1;
                while(j >=0 && s.charAt(i)==s.charAt(j))j--;
                if(s.charAt(i)=='A')
                    p-=a;
                else
                    p-=b;
                if(p<0 ) {
                    break;
                }
                ans =j+1;
                i=j;

            }
            writer.println(ans+1);

        }
    }

    public static void main(String[] args) throws IOException {
        try (Input reader = new StandardInput(); PrintWriter writer = new PrintWriter(System.out)) {
            new B1315().run();
        }
    }

    StandardInput reader;
    PrintWriter writer;

    @Override
    public void run() {
        try {
            reader = new StandardInput();
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    interface Input extends Closeable {
        String next() throws IOException;

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

        default long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        default double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        default int[] readIntArray() throws IOException {
            return readIntArray(nextInt());
        }

        default int[] readIntArray(int size) throws IOException {
            int[] array = new int[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        default long[] readLongArray(int size) throws IOException {
            long[] array = new long[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextLong();
            }
            return array;
        }
    }

    private static class StandardInput implements Input {
        private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        private StringTokenizer stringTokenizer;

        @Override
        public void close() throws IOException {
            reader.close();
        }

        @Override
        public String next() throws IOException {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(reader.readLine());
            }
            return stringTokenizer.nextToken();
        }
    }
}
