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
# https://codeforces.com/problemset/problem/1315/B
# Problem
# Big O:
# Time complexity:
# Space complexity:

# Problem


def crossroad_station_cost(crossroad, bus_ticket, tram_ticket):
    if (crossroad == "A"):
        return bus_ticket
    return tram_ticket


# def find_closest_road_index(bus_ticket, tram_ticket, budget, crossroads):
#     crossroads_length = len(crossroads)
#     cost = 0
#     i = 0
#     previous_station_change = crossroads[i]
#     while (i < crossroads_length - 1):
#         crossroad = crossroads[i]
#         if crossroad != previous_station_change:
#             previous_station_change = crossroad
#             current_cost = crossroad_station_cost(previous_station_change,
#                                                   bus_ticket, tram_ticket)
#             cost += current_cost

def next_crossroad(crossroad):
    if crossroad == "A":
        return "B"
    return "A"


def find_closest_road_index(bus_ticket, tram_ticket, budget, crossroads):
    crossroads_length = len(crossroads)
    i = 0
    current_crossroad = crossroads[0]
    crossroad_changes = [i]
    i += 1
    while (i < crossroads_length - 1):
        # print("====")
        if crossroads[i] != current_crossroad:
            current_crossroad = crossroads[i]
            crossroad_changes.append(i)
        i += 1

    crossroad_changes_length = len(crossroad_changes)
    cost = 0
    cost_change_index = crossroads_length - 1
    # print("==== change ind", cost_change_index)
    j = crossroad_changes_length - 1
    # print("==== ", crossroad_changes, j)

    while cost <= budget and j >= 0:
        crossroad_changes_value = crossroad_changes[j]
        last_crossroad = crossroads[crossroad_changes_value]
        current_cost = crossroad_station_cost(
            last_crossroad, bus_ticket, tram_ticket)
        # print("******", current_cost)
        cost += current_cost
        if (cost <= budget):
            cost_change_index = crossroad_changes[j]
        # print("****** T", cost)
        # print("****** index", cost_change_index)
        j -= 1

    return cost_change_index + 1


# def find_closest_road_index(bus_ticket, tram_ticket, budget, crossroads):
#     crossroads_length = len(crossroads)

#     cost = 0
#     i = crossroads_length - 2
#     cost_change_index = 0

#     if (crossroads[i] != crossroads[i+1] and crossroad_station_cost(crossroads[i], bus_ticket, tram_ticket) > budget):
#         cost = crossroad_station_cost(crossroads[i], bus_ticket, tram_ticket)
#         # if cost > budget:
#         #     print(":::::")
#         cost_change_index = i + 1
#     else:
#         # cost_change_index = i

#         # print("&&&&&", cost)
#         # print("&&&&", cost_change_index)
#         while (i >= 1):
#             crossroad = crossroads[i]
#             previous_crossroad = crossroads[i-1]
#             if previous_crossroad != crossroad:
#                 current_cost = crossroad_station_cost(crossroad,
#                                                       bus_ticket, tram_ticket)
#                 cost += current_cost
#                 cost_change_index = i
#                 # print("=====", cost)
#                 # print("=====", cost_change_index)
#             if cost >= budget:
#                 break
#             i -= 1
#         if (cost_change_index == 0):
#             if (crossroad_station_cost(crossroads[i], bus_ticket, tram_ticket) > budget):
#                 # print("****")
#                 cost_change_index = crossroads_length - 1
#         else:
#             if (i - 2 < 0):
#                 # print("###")
#                 cost_change_index -= 1
#     return cost_change_index + 1
# Read input
test_cases = int(input())
responses = []
for _ in range(test_cases):
    bus_ticket, tram_ticket, budget = (int(x) for x in input().split())
    crossroad = input()
    response = find_closest_road_index(
        bus_ticket, tram_ticket, budget, crossroad)
    responses.append(response)

for response in responses:
    print(response)
