Tý có xâu \(S\) và Q truy vấn. Mỗi truy vấn cho xâu P, đếm số lần P xuất hiện trong \(S\) (kể cả gối lên nhau).

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

• Dòng 1: xâu \(S\) (\(1 \le |S| \le 10^5\)).
• Dòng 2: số nguyên \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp: mỗi dòng là xâu \(P\).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số lần \(P\) xuất hiện trong \(S\).

Ví dụ

Input:

ababa
3
aba
a
bab

Output:

2
3
1

Ràng buộc

• 100% số điểm: \(|S| \le 10^5, Q \le 10^{5}, \sum |P| \le 10^5\).