边界查询

中文题目为机翻，原题目请参考英文题面

给定一个长度为 $n$ 的字符串 $S$ ，由小写英文字母组成。当且仅当 $s1$ 是 $s_1 + s_2$ 的边界，而 $s_3$ 是 $s_2 + s_3$ 的边界时，$S$分割成三个非空子串 $s_1,s_2,s_3$才被认为是好的。当且仅当 $s$ 是 $S$ 的子串，并且存在一个将 $S$ 分割为 $s_1,s_2,s_3$，使得 $s_2 = s$ 的好分区时，我们才说字符串 $s$ 是好字符串。

将字符串的值定义为好子串的个数。当且仅当两个子串的起始位置不同或结束位置不同时，才认为它们是不同的。

给定一个长度为 $m$ 的字符串 $T$，由小写英文字母和 $q$ 个查询组成。在每个查询中，您都会得到两个整数 $l,r$。您需要计算 $T[l\cdots r]$ 的值。

输入

每个测试包含多个测试用例。第一行包含一个整数 $T \: (1 \leq T \leq 60)$ 表示测试用例的数量。

对于每个测试用例，第一行包含三个整数 $n,m,q: (3 \leq n \leq 10^6, 1 \leq m,q \leq 10^6)$ 。

第二行包含长度为 $n$ 的字符串 $S$。

第三行包含长度为 $m$ 的字符串 $T$。

接下来的 $q$ 行分别包含两个整数 $l_i$ 和 $r_i$，表示查询 $(1 \leq l_i \leq r_i \leq m)$。

保证所有测试案例中的 $\sum n, \sum m, \sum q$ 不超过 $10^6$。

输出

对于每个查询，输出一行，用整数表示答案。

请不要输出尾部空格。

示例

1
7 7 2
abacaba
cabacab
1 4
3 7

0
2