Problem C
Search Wizard

You adore word searches, and have been doing them since you were little. You do them so much, you started just picking out words whenever you see a string of text! With a target string $W$ in mind, can you figure out how many times $W$ occurs in the string $S$?

Note that instances of $W$ may overlap partially, but every occurance has a unique starting index in $S$.

Input

The first line consists of a string $W$ ($1\le |W|\le 10$). The second line contains a single integer $M$ ($1\le M\le {10}^5$). The third and final line contains the string $S$ consisting of $M$ words. Consecutive words are separated by a single space. The total length of all words in $S$ is at most ${10}^5$. The only characters that will appear in $W$ and all words in $S$ are lowercase alphabetical characters a - z.

Output

Return an integer of the number of times $W$ occurs in $S$, allowing for overlap.

buzz
8
bee buzz bee buzz bee buzz bee buz

3

aaa
5
aaaaaaaa aa a aaaa aaa

9

aba
3
aba ababa abba

3