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 si=A, if there is a bus station at i-th crossroad, and si=B, if there is a tram station at i-th crossroad. Currently Petya is at the first crossroad (which corresponds to s1) and his goal is to get to the last crossroad (which corresponds to sn).

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 st=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 st=B for all i≤t<j.

For example, if s=“AABBBAB”, a=4 and b=3 then Petya needs:

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 sn) 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≤104).

The first line of each test case consists of three integers a,b,p (1≤a,b,p≤105) — 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 si=A, if there is a bus station at i-th crossroad, and si=B, if there is a tram station at i-th crossroad (2≤|s|≤105).

It is guaranteed, that the sum of the length of strings s by all test cases in one test doesn’t exceed 105.

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>
#define ll long long
using namespace std;

const int maxx=1e5+100;
string s;
int a,b,n;
ll p;

int main()
{
    
	int t,j;
	scanf("%d",&t);
	while(t--)
	{
    
		scanf("%d%d%lld",&a,&b,&p);
		ll sum=0;
		cin>>s;n=s.length();
		s='*'+s;
		for(int i=1;i<=n;)
		{
    
			j=i;
			while(j<=n&&s[j]==s[i]) j++;
			sum+=(ll)(s[i]=='A'?a:b);
			i=j;
			if(i==n) break;
		}
		int i;
		for(i=1;i<=n;)
		{
    
			if(sum<=p) break;
			j=i;
			while(j<=n&&s[j]==s[i]) j++;
			sum-=(ll)(s[i]=='A'?a:b);
			i=j;
			if(i==n) break;
		}
		cout<<min(i,n)<<endl;
	}
	return 0;
}

努力加油a啊，(^o)/~