#include <bits/stdc++.h>
using namespace std;
bool isprime(long long n) {
  if (n == 1) return false;
  if (n == 2) return true;
  for (long long i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
long long poww(long long b, long long e) {
  if (e == 0)
    return 1;
  else if (e % 2 == 0) {
    long long a = pow(b, e / 2);
    return a * a;
  } else {
    long long a = pow(b, e / 2);
    return b * a * a;
  }
}
long long powm(long long x, long long y, long long m = 1000000007) {
  x = x % m;
  long long res = 1;
  while (y) {
    if (y & 1) res = res * x;
    res %= m;
    y = y >> 1;
    x = x * x;
    x %= m;
  }
  return res;
}
long long modInverse(long long a, long long m = 1000000007) {
  return powm(a, m - 2, m);
}
void print(vector<long long> v) {
  for (long long i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
}
void print(long long arr[]) {
  long long size = *(&arr + 1) - arr;
  for (long long i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
}
string to_bin(long long n) {
  string res = "";
  long long i = 0;
  while (n > 0) {
    if (n % 2 == 1) {
      res = res + '1';
    } else {
      res = res + '0';
    }
    n /= 2;
    i++;
  }
  reverse(res.begin(), res.end());
  return res;
}
long long to_dec(string second) {
  long long n = second.size(), ans = 0, temp = 1;
  for (long long i = n - 1; i >= 0; i--) {
    long long x = second[i] - '0';
    ans += x * temp;
    temp *= 2;
  }
  return ans;
}
void result(bool first) {
  if (first)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}
void solve() {
  long long a, b, p;
  cin >> a >> b >> p;
  string second;
  cin >> second;
  reverse(second.begin(), second.end());
  long long n = second.length();
  long long ind = 1;
  long long maxi;
  for (long long i = 1; i < n; i++) {
    char ch = second[i];
    if (second[i] == 'B') {
      if (p >= b) {
        p -= b;
        if (i != n - 1) {
          while (second[i + 1] == 'B') {
            i++;
          }
        }
        ind = i + 1;
      } else
        break;
    } else if (second[i] == 'A') {
      if (p >= a) {
        p -= a;
        if (i != n - 1) {
          while (second[i + 1] == 'A') {
            i++;
          }
        }
        ind = i + 1;
      } else
        break;
    }
  }
  long long ans = n - ind + 1;
  cout << ans << endl;
}
int32_t main() {
  ios_base::sync_with_stdio();
  cin.tie(0);
  cout.tie(0);
  long long tests;
  cin >> tests;
  while (tests--) solve();
}

### Prompt

Please formulate a CPP solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool isprime(long long n) {
  if (n == 1) return false;
  if (n == 2) return true;
  for (long long i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}
long long poww(long long b, long long e) {
  if (e == 0)
    return 1;
  else if (e % 2 == 0) {
    long long a = pow(b, e / 2);
    return a * a;
  } else {
    long long a = pow(b, e / 2);
    return b * a * a;
  }
}
long long powm(long long x, long long y, long long m = 1000000007) {
  x = x % m;
  long long res = 1;
  while (y) {
    if (y & 1) res = res * x;
    res %= m;
    y = y >> 1;
    x = x * x;
    x %= m;
  }
  return res;
}
long long modInverse(long long a, long long m = 1000000007) {
  return powm(a, m - 2, m);
}
void print(vector<long long> v) {
  for (long long i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
}
void print(long long arr[]) {
  long long size = *(&arr + 1) - arr;
  for (long long i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
}
string to_bin(long long n) {
  string res = "";
  long long i = 0;
  while (n > 0) {
    if (n % 2 == 1) {
      res = res + '1';
    } else {
      res = res + '0';
    }
    n /= 2;
    i++;
  }
  reverse(res.begin(), res.end());
  return res;
}
long long to_dec(string second) {
  long long n = second.size(), ans = 0, temp = 1;
  for (long long i = n - 1; i >= 0; i--) {
    long long x = second[i] - '0';
    ans += x * temp;
    temp *= 2;
  }
  return ans;
}
void result(bool first) {
  if (first)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}
void solve() {
  long long a, b, p;
  cin >> a >> b >> p;
  string second;
  cin >> second;
  reverse(second.begin(), second.end());
  long long n = second.length();
  long long ind = 1;
  long long maxi;
  for (long long i = 1; i < n; i++) {
    char ch = second[i];
    if (second[i] == 'B') {
      if (p >= b) {
        p -= b;
        if (i != n - 1) {
          while (second[i + 1] == 'B') {
            i++;
          }
        }
        ind = i + 1;
      } else
        break;
    } else if (second[i] == 'A') {
      if (p >= a) {
        p -= a;
        if (i != n - 1) {
          while (second[i + 1] == 'A') {
            i++;
          }
        }
        ind = i + 1;
      } else
        break;
    }
  }
  long long ans = n - ind + 1;
  cout << ans << endl;
}
int32_t main() {
  ios_base::sync_with_stdio();
  cin.tie(0);
  cout.tie(0);
  long long tests;
  cin >> tests;
  while (tests--) solve();
}

```