19357번 - A Text Problem 다국어

문제

The string $A$ occurs in the string $B$ at position $i$ with at most one mistake if and only if either $A$ occurs in $B$ at position $i,ドル or there exists a string $A'$ obtained from $A$ by replacing the letter at a single position with a different letter such that $A'$ occurs in $B$ at position $i$.

You are given a string $T$ and a series of queries. Each query is a string for which you should compute the number of positions at which it occurs in $T$ with at most one mistake.

입력

The first line of input contains the number of test cases $z$. The descriptions of the test cases follow.

The first line of each test case contains a string of length between 1ドル$ and 200ドル,000円$ consisting of lowercase Latin letters: the string $T$. The next line contains one integer $q$: the number of queries. Each of the following $q$ lines contains a nonempty string consisting of lowercase Latin letters: a query. The sum of lengths of all queries in a test case is at most 200ドル,000円$.

The sum of lengths of all strings appearing in all test cases (including queries) does not exceed 1ドル,200円,000円$.

출력

For each query, output the number of positions in $T$ at which the query occurs with at most one mistake.

제한

힌트