Note: The following problem, Uranus, may be easier if you prefer solving in order of increasing difficulty.
Christiaan Huygens was the first to propose there was a ring surrounding Saturn, in 1655. He did this by publishing his claim as an anagram: aaaaaaacccccdeeeeehiiiiiiillllmmnnnnnnnnnooooppqrrstttttuuuuu. Only three years later did he have enough evidence to publish the true claim: Annulo cingitur, tenui, plano, nusquam cohaerente, ad eclipticam inclinato ("It is encircled by a thin, flat ring, nowhere touching, inclined to the ecliptic").
Shani recently became inspired by Huygens and published some similar anagrammed claim. Unfortunately, it was mostly a joke, but now the research committee is calling upon her to back it up.
Luckily, she does have some data that she has yet to publish. Specifically, she has $$$1 \le n \le 1000$$$ data points, each a string $$$s_i$$$ with $$$1 \le |s_i| \le 100$$$. She may publish any subset of these data points, and once published, she knows the committee will concatenate them in their original order (the data points are dated). Her original claim is a string $$$t$$$ with $$$1 \le |t| \le 20$$$. The committee will then count how many times $$$t$$$ occurs as a substring in the published data (overlaps are counted), and for each occurrence she will earn one reputation score.
Report the maximum reputation score Shani can get.
The first line contains a string $$$t$$$ $$$(1 \le |t| \le 20)$$$ — Shani's original claim.
The next line contains an integer $$$n$$$ $$$(1 \le n \le 1000)$$$ — the number of data points.
The next $$$n$$$ lines each contain a non-empty string $$$s_i$$$ $$$(1 \le |s_i| \le 100)$$$ — the $$$i$$$-th data point, already listed in the order they were recorded.
All strings consist only of lowercase English letters.
Print a single integer — the maximum reputation score Shani can obtain.
lol3ololololo
3
ababac3abababaabac
1
For the first sample, publishing all three data points gives 3 reputation score: $$$\text{o}\color{red}{\text{lol}}\text{ololo}$$$ $$$\text{olo}\color{red}{\text{lol}}\text{olo}$$$ $$$\text{ololo}\color{red}{\text{lol}}\text{o}$$$
For the second, publishing the first and the last gives 1 reputation score: $$$\text{ab}\color{red}{\text{ababac}}$$$
