13856번 - Favorite music 다국어

Al likes music a lot. He has n favorite music fragments he particularly enjoys listening to. It is well known that music can be expressed using notes. For simplicity, we’ll ignore pauses, different note durations and octaves. We’ll assume that a music fragment is just a non-empty sequence of notes (without chords, so no two notes are played at the same time) in the common letter notation:

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

What is better than listening to some favorite music? Only listening to more favorite music! Unfortunately, Al doesn’t have a lot of time for that. Therefore, he’d like to know how much time does he need to hear a couple of his favorite fragments at a time. These fragments may overlap, but the notes in both of them must go in the same order and without any insertions in between.

The first line contains an integer n (1 ≤ n ≤ 3 × 10⁵ ) – the number of music fragments. Each of the next n lines contains a sequence of notes without spaces describing one fragment. It’s guaranteed that all fragments are different. The total length of the strings representing all the fragments is not greater than 3 × 10⁵ . The next line contains an integer q (1 ≤ q ≤ 10⁵ ) – the number of questions Al has in mind. Each of the next q lines contains two different fragment indices. Fragments are numbered from 1 to n as they appear in the input.

For each question, print on a separate line the minimum time needed to hear both given fragments. Assume that each note lasts for one time interval.