Cho xâu \(S\), đếm số xâu con phân biệt bắt đầu bằng một ký tự cụ thể.

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

• Dòng 1: xâu \(S\) (\(1 \le |S| \le 2000\)).
• Dòng 2: số nguyên \(Q\).
• \(Q\) dòng tiếp: một ký tự c cần truy vấn.

Định dạng đầu ra

• Với mỗi ký tự, in ra số xâu con phân biệt bắt đầu bằng c.

Ví dụ

Input:

ababa
3
a
b
c

Output:

4
4
0

Ràng buộc

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