给一个字符串 $s$ 和 $t$。每次询问 $s$ 的一个子串，问与 $t$ 的编辑距离。

这里的编辑距离定义与平时定义不完全一样：每次可以从某个串中插入，删除字符，问最少多少次操作可以使两个串相同。

输入格式

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

第二行一个字符串 $t$，保证 $s$, $t$ 都由小写字母构成。

接下来一行一个数字 $q$ 表示询问次数。

接下来 $q$ 行，每行两个整数 $l, r$ 表示 $s[l \dots r]$ 与 $t$ 的距离，$s$ 下标从 $1$ 开始。

输出格式

$q$ 行，每行一个整数，表示答案。

样例输入1

qaqaqwqaqaq
qaqwqaq
3
1 7
2 8
3 9`</pre>

### 样例输出1

<pre>`4
2
0

样例输入输出2

见下发文件。

数据范围

$20\%$, $|s| \leq 1000, q\leq 1000$。

$40\%$, $|s| \leq 1000$。

$100\%$, $1\leq |s| \leq 10^5, 1\leq q \leq 10^5, 1\leq |t|\leq 20$。