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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const long long int inf = 1e9 + 7;
const long long int mod = 1e9 + 7;
map<int, int>::iterator it;
long long int read() {
  long long int x;
  scanf("%lld", &x);
  return x;
}
string c2s(char c) {
  string re = "0";
  re[0] = c;
  return re;
}
long long int printv(vector<long long int> V) {
  cout << V.size() << ": ";
  for (long long int i = 0; i < V.size(); i++) cout << V[i] << " ";
  puts("");
}
long long int gcd(long long int x, long long int y) {
  while (x % y) {
    long long int t = x % y;
    x = y;
    y = t;
  }
  return y;
}
long long int readv(vector<long long int>& V) {
  for (long long int i = 0; i < ((long long int)V.size()); i++) V[i] = read();
}
bool isprime(long long int x) {
  for (long long int i = 2; i * i <= x; i++)
    if (x % i == 0) return false;
  return true;
}
void pcheck(long long int x) { (x == 0) ? puts("NO") : puts("YES"); }
struct node {
  long long int id, s, c;
  friend bool operator<(node a, node b) {
    if (a.s != b.s)
      return a.s > b.s;
    else
      return a.c > b.c;
  }
};
node mk(long long int x, long long int y, long long int z) {
  node re;
  re.id = x;
  re.s = y;
  re.c = z;
  return re;
}
const long long int N = 5e5 + 5;
long long int a[N], l[N], r[N];
int main() {
  long long int ca = read();
  for (long long int ci = 0; ci < ca; ci++) {
    long long int a = read(), b = read(), v = read();
    string t;
    cin >> t;
    vector<long long int> dp(t.length());
    t[((long long int)t.size()) - 1] =
        'A' + 'B' - t[((long long int)t.size()) - 1];
    for (int i = t.length() - 2; i >= 0; i--)
      if (t[i] == t[i + 1] && i + 2 != ((long long int)t.size()))
        dp[i] = dp[i + 1];
      else {
        dp[i] = dp[i + 1] + (t[i] == 'A' ? a : b);
      }
    long long int ans = 0;
    for (int i = 0; i < ((long long int)t.size()); i++) {
      if (dp[i] <= v) {
        ans = i + 1;
        break;
      }
    }
    cout << ans << endl;
  }
}
