题目描述
给出只包含小写字母 $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$ 的最长公共子串长度。
样例
input
aaba
aaaabbbaa
3
1 4
1 3
2 4output
3
3
2
数据范围与提示
| 测试点编号 | $\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$ |