Given a string $s$ and $n$ strings $p_i$, find the number of occurrences of each string $p_i$ in $s$. Note that the definition of equality between two strings is slightly modified.

Given a constant $k$, two strings $a$ and $b$ are considered equal if:

1. $|a| = |b|$;
2. For all indices $i$ and $j$ where $a_i \neq b_i$ and $a_j \neq b_j$, the condition $|i-j| < k$ is satisfied.

If $|a| = |b| \le k$, then $a = b$ is always considered true.

Input

The first line contains an integer $k$.

The second line contains a string $s$.

The third line contains an integer $n$, followed by $n$ lines, each containing a string $p_i$.

All characters have ASCII values between $33$ and $126$.

Output

Output $n$ lines, representing the number of occurrences of each $p_i$ in $s$.

Examples

Input 1

1
xyz
3
xz
y
xzy

Output 1

2
3
0

Note 1

For $p_1$, $xz = xy$ and $xz = yz$ because there is only one position difference in each case.

For $p_2$, $y = x$, $y = y$, and $y = z$ follow the same logic.

For $p_3$, $xzy \neq xyz$ because the maximum difference is $1$, which does not satisfy $< k = 1$.

Subtasks

For $20\%$ of the data, $|s|, \sum |p_i| \le 10^3$;

For another $20\%$ of the data, $n \le 100$;

For another $20\%$ of the data, $|s|, \sum |p_i| \le 5 \cdot 10^4$;

For $100\%$ of the data, $|s|, \sum |p_i| \le 2 \cdot 10^5$.