Cho một dãy chữ cái viết hoa. Bạn Minh sẽ viết đi viết lại dãy này k lần để thành một dãy mới. Bạn Lộc muốn biết số chữ cái c xuất hiện trong n chữ cái đầu tiên của dãy mới. Hãy giúp bạn ấy tìm ra câu trả lời.

Mô tả đầu vào

• Dòng đầu gồm T là số test.
• Dòng đầu mỗi test chứa dãy chữ cái đã cho với độ dài không quá 100 chữ.
• Dòng thứ hai mỗi test chứa lần lượt ba giá trị k, n, c.

Ràng buộc

• \(1 \leq T \leq 100\) số lượng dãy chữ cái đã cho (mỗi dãy có độ dài không quá 100 chữ)
• \(1 \leq k \leq 10^5\)
• \(1 \leq n \leq k\) là độ dài dãy đã cho

Mô tả đầu ra

• In ra kết quả cần tìm trên một dòng với mỗi test.

2
ABA
3 7 B
BHD
4 6 E

2
0