Cho xâu kí tự ~S~ (chỉ có các kí tự là kí tự latin in hoa từ 'A' đến 'Z'), rồi điền từng kí tự của ~S~ (từ trái qua phải) vào các ô của kim tự tháp như hình bên.

Yêu cầu: Cho xâu kí tự ~S~ và số tầng ~k~ của kim tự tháp. Hãy xác định kí tự ~c~ xuất hiện bao nhiêu lần ở tầng thứ ~k~ của kim tự tháp.

Input

• Dòng 1: Chứa xâu kí tự ~S~ (chỉ có các kí tự là kí tự latin in hoa từ 'A' đến 'Z'), độ dài ~S \le 10^4~;
• Dòng 2: Chứa số nguyên dương ~m~ là số lượng các yêu cầu cần thực hiện;
• ~m~ dòng tiếp theo: mỗi dòng chứa kí tự ~c~ và số nguyên dương ~k~ là yêu cầu cần xác định kí tự ~c~ xuất hiện bao nhiêu lần ở tầng thứ ~k~ của kim tự tháp.

Output

• Gồm ~m~ dòng là kết quả ứng với các yêu cầu cần tìm.

Sample Input 1

DUYENHAI
3
5 I
2 Y
4 A

Sample Output 1

0
1
1