对于两个字符串 $S$ 和 $T$，你可以进行任意次数的以下操作：选择字符串 $S$ 或 $T$，在任意位置插入或删除一个字符。两个字符串 $S$ 和 $T$ 之间的距离定义为使 $S$ 和 $T$ 相等所需的最少操作次数。

给定两个字符串 $A[1..n]$ 和 $B[1..m]$，以及 $q$ 次询问。

在每次询问中，给定两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)。你需要求出连续子串 $A[l_i..r_i]$ 与整个字符串 $B$ 之间的距离。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。每个测试用例： 第一行包含一个由 $n$ ($1 \le n \le 100\,000$) 个小写英文字母组成的字符串 $A$。 第二行包含一个由 $m$ ($1 \le m \le 20$) 个小写英文字母组成的字符串 $B$。 第三行包含一个整数 $q$ ($1 \le q \le 100\,000$)，表示询问次数。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)，描述一次询问。

输出格式

对于每次询问，输出一行，包含一个整数，表示答案。

样例

样例输入 1

1
qaqaqwqaqaq
qaqwqaq
3
1 7
2 8
3 9

样例输出 1

4
2
0