Description

Holmes received a document from Planet X, consisting entirely of lowercase letters.

His assistant provided another document: a list of many passwords of length $8$.

Holmes found that these passwords were shuffled and hidden in the previous document.

Please write a program to search, in the first document, for positions where hidden passwords may appear. You must consider all permutations of each password.

Input Format

The first line contains a string $s$, consisting only of lowercase letters, with length less than $1024 \times 1024$.

The next line contains an integer $n$, indicating that there are $n$ lines of passwords below, where $1 \le n \le 1000$.

The next $n$ lines each contain a string, all consisting of lowercase letters, each of length $8$.

Output Format

Output one integer, representing the total number of matches in $s$ of all permutations of the password on each line.

aaaabbbbaabbcccc
2
aaaabbbb
abcabccc

4

Hint

The first password matches $3$ times, and the second password matches $1$ time, for a total of $4$ times.

Time limit: 3 seconds, 512 MB. Lanqiao Cup 2015, 6th National Finals.

Translated by ChatGPT 5