이름날

당신의 친구는 돈을 좋아한다. 친구는 자신의 이름날이 되면 친절한 이모에게서 돈을 받기 때문에, 자신의 이름날이 오는 것을 무척 좋아한다.

마침 오늘은 친구의 이름날이며, 친구는 다음 이름날이 올 때까지 다시 꼬박 일 년을 기다리지 않을 방법을 고민하고 있다. 당신은 친구를 도와 달라는 부탁을 받았다.

친구는 가능한 한 빨리 다시 이름날을 맞기 위해 자신의 이름에서 정확히 한 글자를 바꾸려고 한다. 다가오는 일 년의 이름날 목록이 주어질 때, 친구가 얼마나 빨리 다시 이름날을 맞을 수 있는지 결정하도록 도와주자. 문자를 추가하거나 삭제하는 것은 금지되며, 정확히 한 문자만 정확히 하나의 다른 문자로 바꿀 수 있다.

위에 나열된 허용 행동으로 만들 수 있는 이름을 찾는 것이 불가능하다면, 친구는 그냥 꼬박 일 년을 기다려야 한다.

채점

당신의 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한 | 기타

1 | 53 |$1 \le N \le 50$|

2 | 47 |$1 \le N \le 10\,000$|

입력은 친구의 이름인 하나의 문자열로 시작한다. 그다음 줄에는 다가오는 일 년의 날짜 수를 나타내는 정수 $N$이 주어진다. 그 뒤에는 다가오는 일 년의 각 날짜에 해당하는 이름날을 나타내는 문자열 $N$개가 주어진다.

$N$번째 이름은 항상 친구의 이름이다. 오늘이 친구의 이름날이므로 정확히 일 년 뒤에도 다시 이름날이기 때문이다. 입력의 이름은 문자 a-z만으로 이루어지고 공백을 포함하지 않으며 길이는 최대 10자이다. 다가오는 일 년의 모든 이름은 서로 다르다.

친구가 이름을 속여 바꾸도록 도와줄 때, 다시 이름날이 되기까지 걸리는 최소 날짜 수를 한 줄에 하나의 정수로 출력한다.

첫 번째 예제 입력에서 친구의 이름은 anna이다. 친구는 자신의 이름에 있는 두 번째 n을 j으로 바꾸어 이름 anja을 만들 수 있으며, 따라서 예상보다 이틀 일찍 이름날을 맞는다. 그러므로 답은 3이다. 두 번째 예제 입력에서는 위에 나열된 행동으로 다른 이름을 만드는 것이 불가능하므로, jan은 꼬박 일 년, 즉 3일을 기다려야 한다.