CF2232C1.Seating Arrangement (Easy Version)

This is the Easy version of the problem. The difference between the versions is that in this version, the constraints on $n$, $x$, $s$, $t$ are smaller. 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.

这是本题的简单版本。两个版本的区别在于：在本版本中，$n$、$x$、$s$、$t$ 的约束更小。仅当您已解决本题的所有版本后，才可进行 hack。

Alice 的朋友们来到派对现场，现在他们正排成一队依次入场。

派对现场共有 $x$ 张桌子，每张桌子有 $s$ 个座位。每个座位至多容纳一人。

每位朋友具有以下三种性格之一：

• 内向者（I）：必须坐在一张空桌子上；
• 外向者（E）：必须坐在一张非空桌子上；
• 中性者（A）：可以坐在任意桌子上。

初始时，所有座位均为空。但由于 Alice 正在吃蛋糕，她的朋友们已自行排好队，且 Alice 无法更改该队伍顺序。对于队伍中的每个人，Alice 必须为其分配一张桌子，或将其拒之门外。每位朋友必须在下一位朋友被分配桌子之前完成就座。

为了使派对充满欢乐，Alice 希望尽可能多地让朋友们入座。请帮她求出最多能有多少位朋友成功入座。

注意：一旦某位朋友被安排就座，其座位便不可再移动，即使之后该座位不再符合其性格要求，也仍视为有效。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). 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 3000$) – 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 $3000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$x$ 和 $s$（$1 \le n,x,s \le 3000$），分别表示爱丽丝的朋友数量、桌子数量以及每张桌子的座位数。第二行包含一个长度为 $n$ 的字符串 $u$，仅由字母 A、E 和 I 组成，分别代表双性人格者（ambivert）、外向者（extrovert）和内向者（introvert）。

保证所有测试用例的 $n$ 值之和不超过 $3000$。

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

对于每个测试用例，输出一个整数：最多可以坐多少人。

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.

在第一个测试用例中，共有 $2$ 张桌子，每张桌子有 $2$ 个座位。以下是实现最多就座人数的一种方式。

第一个人是外向者。由于所有桌子均为空，此人必须离开聚会。

第二个人是内向者。爱丽丝可将其安排至第一张空桌子。

第三个人是中间型人格者。爱丽丝可将其安排至第一张桌子。

第四个人是内向者。爱丽丝可将其安排至第二张空桌子。

第五个人是外向者。爱丽丝可将其安排至第二张非空桌子。

因此，共有四人就座于聚会中。该数目已达最大值，因为聚会上仅有四个座位。