A85927.「BJOI2020」封印

给出只包含小写字母 $a,b$ 的两个字符串 $s, t$，$q$ 次询问，每次询问 $s[l \dots r]$ 和 $t$ 的最长公共子串长度。

输入共 $q+3$ 行。

第一行一个字符串 $s$。

第二行一个字符串 $t$。

第三行一个整数 $q$。

接下来的 $q$ 行，每行两个整数 $l_i, r_i(1\le l_i \le r_i \le |s|)$，表示一次询问。

输出共 $q$ 行。

第 $i$ 行表示 $s[l_i \dots r_i]$ 和 $t$ 的最长公共子串长度。

测试点编号	$\vert s\vert , \vert t\vert \le $	$q\le$
$1$	$50$	$50$
$2,3$	$2\times 10^3$	$2\times 10^3$
$4,5$	$2\times 10^5$	$10$
$6\sim 10$	$2\times 10^5$	$2\times 10^5$