시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 6 6 54.545%

문제

단어가 N개 있는 데이터베이스가 있다.

이 데이터베이스에서 어떤 단어를 찾을 때 사용하는 알고리즘은 상당히 원시적이다.

이 알고리즘은 단어 W와 데이터베이스에 있는 단어를 하나씩 비교한다. 단어를 비교할 때는, 각 단어의 가장 앞에서부터 다른 문자가 나오거나, 한 단어의 끝이 나올 때 까지 하나씩 비교한다. 만약, 단어 W를 찾으면 이 알고리즘은 그 즉시 종료된다.

단어의 길이는 단어를 검색하기 전에 알 수 없으므로, 마지막 글자도 비교를 해야 단어가 끝났다는 것을 알게 된다. 즉, abc와 abcd가 있을 때, abc의 4번째 글자와 abcd의 4번째 글자를 비교할 때 단어가 서로 다르다는 것을 알 수 있는 것이다. 마찬가지로 단어가 같은 것도 마지막 글자 다음 글자를 비교해야 알 수 있다. abc와 abc가 있을 때, abc의 4번째 글자와 abc의 4번째 글자가 모두 없는 것으로 같으므로 단어를 찾았다는 뜻이다.

단어 목록이 주어지고, 검색하려고 하는 단어가 주어졌을 때, 몇 번 비교만에 단어를 찾을 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 30,000)

다음 N개의 줄에는 데이터베이스에 있는 단어가 주어진다. 단어를 검색할 때, 입력으로 주어진 단어 순서를 그대로 사용해야 한다. 또한, 모든 단어는 다르다.

다음 줄에는 검색하려고 하는 단어의 개수 Q가 주어진다. (1 ≤ Q ≤ 30,000)

다음 Q개 줄에는 검색하려고 하는 단어가 주어진다.

모든 단어는 알파벳 소문자로 이루어져 있고, 길이는 30보다 작다.

출력

Q개 줄에 걸쳐, 각 단어를 검색하는데 필요한 비교의 수를 출력한다.

예제 입력

8
majmunica
majmun
majka
malina
malinska
malo
maleni
malesnica
3
krampus
malnar
majmun

예제 출력

8
29
14

힌트

krampus를 검색하려면 데이터베이스에 있는 단어의 첫 번째 글자만 비교하면 되므로 8번만 비교하면 된다. 

malnar를 검색하려면, 처음 3단어는 3번, 뒤의 5단어는 4번 검색하면 되므로 29번 비교하면 된다.

majmun을 검색하려면, 14번 검색하면 된다. 첫 번재 단어 "majmunica"와 7번 비교를 하고, 길이가 다르므로 다음 단어와 비교한다. 다음 단어에서 7번 비교를 하면 되므로 14번이다. 단어를 찾은 후에는 더이상 검색을 하지 않으므로 더 검색할 단어는 없다.