给定一个由小写英文字母组成的长度为 $n$ 的字符串 $S$。若 $S$ 的一个划分为三个非空子串 $s_1, s_2, s_3$，且满足 $s_1$ 是 $s_1 + s_2$ 的 border，且 $s_3$ 是 $s_2 + s_3$ 的 border，则称该划分为一个“好划分”。若字符串 $s$ 是 $S$ 的子串，且存在 $S$ 的一个好划分使得 $s_2 = s$，则称 $s$ 为“好字符串”。

定义一个字符串的“值”为其所有好子串的数量。若两个子串的起始位置不同或结束位置不同，则视为不同的子串。

给定一个由小写英文字母组成的长度为 $m$ 的字符串 $T$ 以及 $q$ 次询问。每次询问给定两个整数 $l, r$，你需要计算 $T[l \dots r]$ 的值。

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 60$)，表示测试数据组数。

对于每组测试数据，第一行包含三个整数 $n, m, q$ ($3 \le n \le 10^6, 1 \le m, q \le 10^6$)。 第二行包含一个长度为 $n$ 的字符串 $S$。 第三行包含一个长度为 $m$ 的字符串 $T$。 接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$，表示一次询问 ($1 \le l_i \le r_i \le m$)。

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

输出格式

对于每次询问，输出一行，包含一个整数，表示该询问的答案。 请不要输出多余的行末空格。

样例

输入 1

1
7 7 2
abacaba
cabacab
1 4
3 7

输出 1

0
2