human
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:


  * 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...
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is the Python program you requested.

from sys import stdin
from collections import deque
mod = 10**9 + 7
import sys
import random
# sys.setrecursionlimit(10**6)
from queue import PriorityQueue
# def rl():
#     return [int(w) for w in stdin.readline().split()]
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt,factorial,gcd,log2,inf,ceil
# map(int,input().split())
# # l = list(map(int,input().split()))
# from itertools import permutations
import heapq
# input = lambda: sys.stdin.readline().rstrip()
input = lambda : sys.stdin.readline().rstrip()
from sys import stdin, stdout
from heapq import heapify, heappush, heappop
from itertools import permutations
from math import factorial as f

def ncr(x, y):
    return f(x) // (f(y) * f(x - y))

t = int(input())

for _ in range(t):

    a,b,p = map(int,input().split())

    s = list(input())
    ans = []

    i = 0
    while i<len(s):
        cnt = 0
        init = i
        if s[i] == 'A':
          cnt = 0
          while s[i] == 'A':
            cnt+=1
            i+=1
            if i == len(s):
                break


          final = i
          if final == len(s):
              if init+1 == final:
                ans.append([0,init,final])
              else:
                  ans.append([a,init,final])
          else:
              ans.append([a,init,final])

        else:
          cnt = 0
          init = i
          while s[i] == 'B':
            cnt+=1
            i+=1
            if i == len(s):
                break

          final = i
          if final == len(s):
              if init+1 == final:
                  ans.append([0,init,final])
              else:
                  ans.append([b,init,final])
          else:
              ans.append([b,init,final])

    ans.reverse()
    pref = [[0,0,0]]
    for i in ans:
        pref.append([pref[-1][0]+i[0],i[1],i[2]])

    ans = len(s)
    for i in range(1,len(pref)):
        if pref[i][0]<=p:
            if pref[i][2] != len(s):

              ans = pref[i][1]+1
    ...