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.