给出只包含小写字母 的两个字符串 ， 次询问，每次询问 和 的最长公共子串长度。

输入共 行。

第一行一个字符串 。

第二行一个字符串 。

第三行一个整数 。

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

输出共 行。

第 行表示 和 的最长公共子串长度。