Al 非常喜欢音乐。他有 $n$ 个特别喜欢听的音乐片段。众所周知，音乐可以用音符来表示。为了简单起见，我们将忽略休止符、不同的音符时值和八度。我们假设一个音乐片段只是一个非空的音符序列（没有和弦，因此不会同时演奏两个音符），采用常见的字母表示法：

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

有什么比听一些喜欢的音乐更好呢？那就是同时听更多喜欢的音乐！不幸的是，Al 没有太多时间。因此，他想知道一次性听完两个他最喜欢的片段最少需要多少时间。这两个片段可以重叠，但每个片段在合并后的序列中必须保持原样连续出现，中间不能插入其他音符。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 3 \times 10^5$) —— 音乐片段的数量。

接下来的 $n$ 行，每行包含一个不带空格的音符序列，描述一个片段。保证所有片段互不相同。代表所有片段的字符串总长度不超过 $3 \times 10^5$。

下一行包含一个整数 $q$ ($1 \le q \le 10^5$) —— Al 想要提问的问题数量。

接下来的 $q$ 行，每行包含两个不同的片段编号。片段按在输入中出现的顺序从 $1$ 到 $n$ 进行编号。

输出格式

对于每个问题，在单独的一行中输出听完给定的两个片段所需的最短时间。假设每个音符持续一个时间单位。

样例

输入样例 1

3
ABCAB
AC
ACAB
3
1 2
1 3
2 3

输出样例 1

7
7
4

输入样例 2

5
EBEBGF#DEEBEBF#GABBEBECBGAAADAEADA
EECAGGECDECBAACDEECAAAFABCAGAAAA
EECAGGECDECBAACDECEFGCGFEFDCDDDD
G#A#CDD#FD#DCA#G#A#CDD#FDD#FGG#A#G#GFD#DD#FGG#A#
GG#A#CDD#DCFD#DGFD#DCA#CDD#FGFD#A#CA#G#GFD#DCC
3
2 3
4 5
5 1

输出样例 2

64
63
66