Cho xâu \(S\) và \(Q\) truy vấn, mỗi truy vấn cho một ký tự c. Đếm số xâu con phân biệt bắt đầu bằng c trong xâu \(S\).

Định dạng đầu vào

• Dòng 1: xâu \(S\).
• Dòng 2: số \(Q\).
• Q dòng: ký tự c.

Định dạng đầu ra

• Mỗi truy vấn in một số nguyên.

Ví dụ

Input:

ababa
3
a
b
c

Output:

4
4
0

Ràng buộc

• 100% số điểm: \(|S| \le 2000, Q \le 26\).