给定一个字符串 ，定义它的 前缀 为字符串 ， 后缀 为字符串 ，其中 。 定义 为对于 ，满足 的字符串 的集合。 中的每个元素都称之为字符串 的 。 有 组询问，每组询问给定 ，求 的 前缀 和 前缀的最长公共 的长度。

输入描述:

在一行上输入一个字符串 ，仅包含小写字母。 在第二行输入一个整数 ，表示询问数量。 接下来 行，第 行输入两个整数 ，描述一次询问。

输出描述:

对于每组询问，在一行上输出一个整数，表示对应最长公共 border 的长度；若不存在公共 border ，输出 。