좋아하는 음악

알은 음악을 아주 좋아한다. 그중에서도 특히 즐겨 듣는 음악 조각이 $n$개 있다.

음악은 음표로 적을 수 있다. 여기서는 쉼표와 음표의 길이, 옥타브를 모두 무시한다. 화음도 없어서 두 음이 동시에 울리는 일은 없다. 그래서 음악 조각은 아래 12개 음 이름을 늘어놓은, 비어 있지 않은 수열이다.

C, C#, D, D#, E, F, F#, G, G#, A, A#, B

조각은 음 이름을 공백 없이 이어 붙여 적는다. 샤프가 붙은 음은 알파벳 뒤에 #을 붙여 적고, 이 두 글자가 하나의 음이다. 예를 들어 A#A는 A#과 A, 두 음으로 이루어진 조각이고, AA#은 A와 A#으로 이루어진 조각이다.

좋아하는 음악을 듣는 것보다 좋은 일은 좋아하는 음악을 더 많이 듣는 것뿐이다. 그런데 알에게는 시간이 넉넉하지 않다. 그래서 조각 두 개를 한 번에 듣는 데 걸리는 시간의 최솟값이 궁금하다. 두 조각은 서로 겹쳐도 되지만, 각 조각의 음은 원래 순서 그대로, 중간에 다른 음이 끼어들지 않게 연속으로 울려야 한다.

질문마다 조각 두 개의 번호가 주어진다. 두 조각을 모두 이 조건대로 담고 있는 음 수열 중 가장 짧은 것의 길이를 구하면 된다. 음 하나를 듣는 데 걸리는 시간은 1이다.

첫째 줄에 음악 조각의 개수 $n$ ($1 \le n \le 3 \times 10^5$)이 주어진다.

다음 $n$개 줄에 조각이 한 줄에 하나씩, 음 이름을 공백 없이 이어 붙인 형태로 주어진다. 모든 조각은 서로 다르다. 조각을 적은 문자열의 길이를 모두 더한 값은 $3 \times 10^5$ 이하이다.

그다음 줄에 질문의 개수 $q$ ($1 \le q \le 10^5$)가 주어진다.

다음 $q$개 줄에 서로 다른 조각 번호 두 개가 주어진다. 조각의 번호는 입력에 나온 순서대로 $1$번부터 $n$번까지이다.

질문마다 두 조각을 모두 듣는 데 필요한 시간의 최솟값을 한 줄에 하나씩 출력한다.