Given a string s and a set of n strings $p_i$.

For each i find the number of occurrences of $p_i$ 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 $t_pt_{p+1}\ldots t_{p+|s|-1}$ are equal with at most one k-length gap.

Strings s and r are equal with at most one k-length gap if:

1. $|s| = |r|$;
2. or all i and j such that $s_i \ne r_i$ and $s_j \ne r_j$, it holds $|i - j| < k$.

Input format

First line of input contains single integer k ($1 \leq k \leq 2 \cdot 10^5$).

Second line of input contains string s ($1 \leq |s| \leq 2 \cdot 10^5$).

Third line contains an integer n ($1 \leq n \leq 2 \cdot 10^5$).

Then follow n lines. The i-th of them contains string $p_i$ ($\sum\limits_{i=1}^{n} |p_{i}| \leq 2 \cdot 10^5$).

s and $p_i$ can contain characters with codes from $33$ to $126$, inclusive.

Output format

Print n lines. The i-th of them should contain the number of occurrences $p_i$ in s with at most one k-length gap.