F. 【Happy Question Round 1 F】前缀

有 个字符串，分别为：

现有 次查询，每次查询区间 到 的字符串的最长公共前缀。

最长公共前缀定义：对于若干字符串，它们从第一个字符开始连续相同的最长前缀长度。例如字符串 、、 的公共前缀为 ，长度为 。

第一行两个整数 。

接下来 行，每行一个字符串 。

接下来 行，每行两个整数 ，表示一次查询。

对于每次查询，输出一行一个整数，表示区间 内所有字符串的最长公共前缀长度。

输入输出样例 #1

输入 #1

3 3
abc
abd
abe
1 3
1 2
2 3

输出 #1

2
2
2

对于 的数据，保证：

• 字符串仅包含小写英文字母。
• 。
• 。

注意本题时间范围，请选用快速的读入方式。