Fine Dining Restaurant

Sanggeun runs a fine dining restaurant. After a nuclear power plant accident people became very afraid of radiation, so the government decided that the radiation in $M$ kinds of ingredients is at a dangerous level and passed a law that keeps those ingredients out of cooking entirely.

Every ingredient carries a serial number made only of the digits 0 to 9. Sanggeun's restaurant makes a single dish, and he knows the serial number of every ingredient that goes into it.

Sanggeun has to check each ingredient for radioactive contamination. He is very lazy, so he concatenates the serial numbers of the ingredients in order into one string $A$ of length $N$, and then only checks whether a banned serial number occurs inside $A$.

Seonyeong, who runs a restaurant nearby, does this check automatically with a robot. Sanggeun asked her and borrowed it.

The robot checks whether the serial number $B$ occurs inside the serial number $A$ in the following order. The length of $B$ is $L$.

• Take digit 1 through digit $L$ of $A$ and compare them with $B$ one digit at a time, front to back. The comparison stops when two digits differ or when the last digit has been compared. If the two strings are equal, the robot shows a success message and ends the check.
• If the check has not ended, compare digit 2 through digit $L+1$ the same way. If they are not equal either, go on with digit 3 through digit $L+2$, then digit 4 through digit $L+3$, in that order.
• The substring that gets cut out is sometimes shorter than $L$. (The length of $A$ is 8 and the check starts at position 5.) Then # is appended until the length is $L$, and the comparison runs on that. For example, position 4 through position 10 of 563232 is 232####. A # is equal to none of the digits 0 to 9.
• If all $N$ starting positions are checked and no equal part is found, the robot shows a failure message and ends the check.

Every time the robot compares two digits, Sanggeun has to pay Seonyeong 1 won.

Find the amount Sanggeun has to pay while the robot checks the banned serial numbers one by one.

The first line contains the length $N$ of the string obtained by concatenating the serial numbers of the ingredients, and the second line contains that string. ($1 \le N \le 100000$)

The third line contains the number of banned ingredients $M$. ($1 \le M \le 50000$) Each of the next $M$ lines contains one banned serial number.

Every serial number consists only of the digits 0 to 9. A single banned serial number is at most $100000$ digits long, and the banned serial numbers are at most $3000000$ digits long in total.

For each banned serial number, print the amount the robot's check costs, one per line, in the order given in the input.