题目描述

给你 $n$ 个字符串，接下来有 $m$ 个询问，每次询问第 $i$ 个字符串与第 $j$ 个字符串的最长公共前缀长度。

两个字符串 $a,b$ 的最长公共前缀是指： 找到最大的长度 $k$，满足 $a$ 和 $b$ 前 $k$ 个位置的字符完全一样。

输入格式

第一行一个整数 $n$，代表字符串个数。

接下来 $n$ 行，每行一个字符串，保证是由小写字母构成。

接下来一行一个整数 $m$, 代表询问个数。

接下来 $m$ 行，每行两个整数， 代表一组询问。

输出格式

输出共 $m$ 行，每行表示一组询问的答案。

4
abcd
cdf
abc
bbc
2
1 3
2 4

3
0

数据规模

对于所有数据，保证 $1≤n,m≤50000, 1≤i,j≤n, i≠j$, $1≤$单个字符串长度$≤10000$, $1≤$所有字符串长度和$≤500000$，字符串均由小写字母构成。