|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||1024 MB||4||3||3||100.000%|
Your friend likes money. When your friend has a name day he or she gets money from their nice aunt, hence your friend really enjoys when they have a name day.
It happens to be your friend's name day today, and your friend is considering how they could avoid having to wait another whole year before it's time for name day again. You've been asked to help out.
Your friend is planning to replace exactly one letter in their name in order to have a name day as soon as possible again. Given a list of name days for the coming year, please help your friend decide how soon they can have a name day again. It's forbidden to add or erase characters, you may only replace exactly one character with exactly one other character.
If it's impossible to find a name that can be reached with the above listed allowed actions, your friend will simply have to wait a whole year.
Input starts with a single string, the name of your friend. Then follows an integer $N$ on one row, the number of days in the coming year. After that follows $N$ strings, the name days for days in the coming year.
The $N$:th name will always be the name of your friend, since it's their name day today and hence also in exactly one year again. The names in the input consist solely of characters
a-z, contain no spaces and are at most 10 characters long. All names for the coming year will be different.
Output a single integer on a single line: the minimum number of days before it's time for name day again, if you help your friend cheat with their name.
$1 \le N \le 50$
$1 \le N \le 10\,000$
anna 5 peter petra anja markus anna
jan 3 petra bengt jan
anya 4 ana hanya enya anya
In the first sample input your friend's name is
anna. She can make the name
anja by replacing the second
n in her name with a
j, and thus she has a name day two days earlier than expected. Thus the answer is 3. In the second sample input it's impossible to create another name using the above listed actions, so
jan will have to wait a whole year, 3 days.