This is the Hard version of the problem. The difference between the versions is that in this version, the constraints on $$$n$$$, $$$x$$$, $$$s$$$, $$$t$$$ are larger. You can hack only if you solved all versions of this problem.

Alice's friends have come to the party, and now they are lining up to enter the party.

There are $$$x$$$ tables at the party with $$$s$$$ seats each. Each seat can only hold one person.

Each friend has one of these three following personalities:

Introverts (I) who have to sit at an empty table
Extroverts (E) who have to sit at a non-empty table
Ambiverts (A) who can sit at any table.

Initially, every seat is empty. However, because Alice was eating cakes, her friends had already formed a line, which Alice cannot change their order. For each person in the line, Alice has to assign them a table or kick them out of the party. Each person is seated before the next person is assigned a table.

Wanting to have a lot of fun at the party, Alice needs to seat as many people as she can at the party. Help her find the maximum number of friends she can have at the party.

Note that once a friend is seated, they are not allowed to move even if they are not seated according to their personality anymore.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$s$$$ ($$$1 \le n,x,s \le 2\cdot 10^5$$$) – the number of Alice's friends, the number of tables, and the number of seats per table. The second line contains a string $$$u$$$ of length $$$n$$$ consisting only of the letters A, E, and I, representing an ambivert, extrovert, and introvert respectively.

It is guaranteed that the sum of $$$n$$$ for all test cases is at most $$$2 \cdot 10^5$$$.

Output

For each test case, output an integer: the maximum number of people seated.

Note

In the first test case, there are $$$2$$$ tables with $$$2$$$ seats each. Here is one of the ways to achieve the maximum number of people seated.

The first person is an extrovert. Since all tables are empty, they have to leave the party.

The second person is an introvert. Alice can assign them to the first table, which is empty.

The third person is an ambivert. Alice can assign them to the first table.

The fourth person is an introvert. Alice can assign them to the second table, which is empty.

The fifth person is an extrovert. Alice can assign them to the second table, which is not empty.

Thus, four people are seated at the party. This is maximal since there are only four seats at the party.

Seating Arrangement (Hard Version)

Examples