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
from collections import Counter as C,defaultdict as D,deque as Q
from operator import itemgetter as I
from itertools import product as P,permutations as PERMUT
from bisect import bisect_left as BL,bisect_right as BR,insort as INSORT
from heapq import heappush as HPUSH,heappop as HPOP
from math import floor as MF,ceil as MC, gcd as MG,factorial as F,sqrt as SQRT, inf as INFINITY,log as LOG
from sys import stdin, stdout
INPUT=stdin.readline
PRINT=stdout.write
L=list;M=map

def Player1():
	print("")

def Player2():
	print("")

def Yes():
	PRINT("Yes\n")

def No():
	PRINT("No\n")

def IsPrime(n):

	for i in range(2,MC(SQRT(n))+1):
		if n%i==0:
			return False
	return True

def Factors(x):

	ans=[]

	for i in range(1,MC(SQRT(x))+1):
		if x%i==0:
			ans.append(i)
			if x%(x//i)==0:
				ans.append(x//i)
	return ans
def CheckPath(source,destination,g):
	visited=[0]*101
	q=Q()
	q.append(source)
	visited[source]=1
	while q:
		node=q.popleft()
		if node==destination:
			return 1
		for v in g[node]:
			if not visited[v]:
				q.append(v)
				visited[v]=1
	return 0
def Sieve(n):
	prime=[1]*(n+1)
	p=2
	while p*p<=n:
		if prime[p]:
			for i in range(p*p,n+1,p):
				prime[i]=0
		p+=1
	primes=[]
	for p in range(2,n+1):
		if prime[p]:
			primes.append(p)
	return primes

def Prefix(a,n):
	p=[]
	for i in range(n):
		if i==0:
			p.append(a[0])
		else:
			p.append(p[-1]+a[i])
	return p
def Suffix(a,n):
	s=[0]*n
	for i in range(n-1,-1,-1):
		if i==n-1:
			s[i]=a[i]
		else:
			s[i]=s[i+1]+a[i]
	return s
def Spf(n):
	spf=[0 for i in range(n)]
	spf[1]=1
	for i in range(2,n):
		spf[i]=i
	for i in range(4,n,2):
		spf[i]=2
	for i in range(3,MC(SQRT(n))+1):
		if spf[i]==i:
			for j in range(i*i,n,i):
				if spf[j]==j:
					spf[j]=i
	return spf

def DFS(g,s,visited,ans):
	visited[s]=1
	
	for u,c in g[s]:

		if visited[u]:
			continue

		if c==ans[s]:

			if c==1:
				ans[u]=2
			else:
				ans[u]=1
		else:
			ans[u]=c
		DFS(g,u,visited,ans)

def Main():

	for _ in range(int(INPUT())):
		a,b,c=M(int,INPUT().split( ))
		s=INPUT();n=len(s)-1
		ans=n;i=n-2
		tmp=0
		d={};d['A']=a;d['B']=b

		while i>=0:
			j=i
			while j>=0 and s[j]==s[i]:
				j-=1
			tmp+=d[s[i]]
			i=j
			if tmp<=c:
				ans=i+2

		PRINT("%d\n"%(ans))





Main()

'mysql -u root -p'