Given a string s and a set of n strings .
For each i find the number of occurrences of in s with at most one k-length gap.
The string s occurs in string t at position p with at most one k-length gap if strings s and are equal with at most one k-length gap.
Strings s and r are equal with at most one k-length gap if:
Input format
First line of input contains single integer k ().
Second line of input contains string s ().
Third line contains an integer n ().
Then follow n lines. The i-th of them contains string ().
s and can contain characters with codes from to , inclusive.
Output format
Print n lines. The i-th of them should contain the number of occurrences in s with at most one k-length gap.