Sau khi thoát khỏi "mê cung", họ cuối cùng cũng tới được công viên, tại công viên họ thấy PhuocThien, bạn của BabyOrange và CandySnowy. PhuocThien rủ hai bạn tham gia bữa tiệc của anh ấy vào ngày mai, và họ đồng ý.
Khi tới nơi tổ chức bữa tiệc, họ thấy bạn bè của PhuocThien đang xếp hàng để vào bữa tiệc.
Bữa tiệc của PhuocThien có \(x\) bàn tại bữa tiệc, mỗi bàn có \(s\) chỗ ngồi, mỗi chỗ chỉ chứa được một người
Mỗi người bạn của PhuocThien có một trong ba tính cách sau:

• Hướng nội (I): Người có tính cách này chỉ ngồi ở bàn trống
• Hướng ngoại (E): Bắt buộc phải ngồi ở bàn không trống (Bàn đã có người ngồi)
• Hướng trung (A): Có thể ngồi ở bất kỳ bàn nào

Ban đầu tất cả các chỗ đều đang trống. Tuy nhiên, vì các bạn đã xếp thành hàng, PhuocThien không thể thay đổi vị trí của các bạn trong hàng. Với mỗi người trong hàng, PhuocThien phải chỉ định cho họ một bàn hoặc... đuổi họ ra khỏi bưa tiệc. Mỗi người được xếp chỗ trước khi người tiếp theo được chỉ định vị trí chỗ ngồi.
Vì PhuocThien đang rất bận cho việc chuẩn bị bữa tiệc, anh ấy liền nhờ BabyOrange và CandySnowy giúp anh trong việc sắp xếp chổ ngồi sao cho càng nhiều người có chổ ngồi càng tốt. Háy giúp BabyOrange và CandySnowy tìm ra số lượng bạn bè tối đa mà cô ấy có thể mời đến bữa tiệc
Lưu ý: khi bạn bè đã ngồi vào chỗ, họ không được phép di chuyển ngay cả khi vị trí đó không còn phủ hợp với tính cách của họ nữa.

Input

• Dòng đầu tiên chứa số lượng truy vấn \(t\) \((1 \le t \le 500)\)
• Mỗi truy vấn chứa hai dòng:
• Dòng đầu tiên chứa 3 số \(n, x, s\) \((1 \le n,x,s \le 3000)\)
• Dòng thứ hai chứa một dãy \(u\) có độ dài \(n\) gồm các ký tự A,E,I

Output

• Với mỗi truy vấn, in ra số lượng người tối đa có chỗ ngồi

Example

1
5 2 2
EIAIE

4

5
20 5 5
AEIEEEEIEAAEIEEEEIEA
8 2 4
AAAAAIEE
8 4 2
AIEAEAAI
8 3 3
AIEAEAAI
4 2 2
IAEE

20
7
7
7
4