Favorite music

Al likes music a lot. He has $n$ favorite music fragments that he especially enjoys.

Music can be written down with notes. Here we ignore rests, note durations and octaves. There are no chords either, so two notes never sound at the same time. A music fragment is therefore a non-empty sequence of the following 12 note names.

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

A fragment is written as its note names joined without spaces. A sharp note is written as a letter followed by #, and those two characters are a single note. For example, A#A is a fragment of the two notes A# and A, while AA# is a fragment of the notes A and A#.

The only thing better than listening to favorite music is listening to more favorite music. Al does not have much time for that, so he wants to know the smallest amount of time it takes to hear two fragments at once. The two fragments may overlap, but the notes of each fragment must sound in their original order, one right after another, with nothing inserted in between.

Each question gives the numbers of two fragments. Find the length of the shortest note sequence that contains both fragments this way. Hearing one note takes one unit of time.

The first line contains the number of music fragments $n$ ($1 \le n \le 3 \times 10^5$).

Each of the next $n$ lines contains one fragment, written as note names joined without spaces. All fragments are different. The sum of the lengths of the strings that describe the fragments is at most $3 \times 10^5$.

The next line contains the number of questions $q$ ($1 \le q \le 10^5$).

Each of the next $q$ lines contains two different fragment numbers. Fragments are numbered from $1$ to $n$ in the order they appear in the input.

For each question, print on its own line the smallest amount of time needed to hear both fragments.