Hide

Problem A
Namnsdag

Languages en sv

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

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

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.

Explanation of sample

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.

Scoring

Your solution will be tested on a number of test case groups. To get points for a group you have to solve all the test cases in that group.

Group

Points

Limits

Other

1

53

$1 \le N \le 50$

 

2

47

$1 \le N \le 10\, 000$

 
Sample Input 1 Sample Output 1
anna
5
peter
petra
anja
markus
anna
3
Sample Input 2 Sample Output 2
jan
3
petra
bengt
jan
3
Sample Input 3 Sample Output 3
anya
4
ana
hanya
enya
anya
3