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\).
• Dòng 2: số \(Q\).
• Q dòng tiếp: ký tự c.

Định dạng đầu ra

• Với mỗi truy vấn in một số nguyên là số xâu con phân biệt bắt đầu bằng c.

Ví dụ

Input:

ababa
1
a

Output:

3

Ràng buộc

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