Bình có một văn bản \(T\) và K từ khóa. Bình muốn đếm số lần mỗi từ khóa xuất hiện trong \(T\) (các lần xuất hiện có thể chồng lấn). Hãy giúp Bình!

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

• Dòng đầu: xâu \(T\) (\(1 \le |T| $\le 10^5\)), gồm chữ cái in thường a..z.
• Dòng hai: số nguyên \(K\) (\(1 \le K $\le 10^5\)).
• \(K\) dòng tiếp theo: mỗi dòng là một từ khóa, tổng độ dài không quá \(10^5\).

Định dạng đầu ra

• In ra \(K\) dòng, dòng thứ i là số lần từ khóa thứ \(i\) xuất hiện.

Ví dụ

Input:

aaaaa
3
a
aa
aaa

Output:

5
4
3

Ràng buộc