厌倦了求解数学方程，DreamGrid 开始尝试解决与字符串相关的方程：对于两个长度相等且由小写英文字母组成的字符串 $x$ 和 $y$，计算 $f(x, y, n)$，其定义为满足 $xz = zy$ 且长度不超过 $n$ 的非空字符串 $z$ 的数量。

DreamGrid 有两个字符串 $s = s_1s_2 \dots s_n$ 和 $t = t_1t_2 \dots t_m$。他想询问关于 $f(t, s[x..(x + m - 1)], y)$ 的值，其中 $s[x..(x + m - 1)]$ 是 $s$ 中从 $s_x$ 开始长度为 $m$ 的子串，$y$ 是给定的数字。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $n$、$m$ 和 $q$ ($1 \le n, m, q \le 10^5, m \le n$)，分别表示字符串 $s$ 的长度、字符串 $t$ 的长度以及询问次数。

第二行包含 $n$ 个小写英文字母，表示字符串 $s$。第三行包含 $m$ 个小写英文字母，表示字符串 $t$。

接下来的 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i \le n + 1 - m, 1 \le y_i \le 10^{18}$)，表示第 $i$ 个询问。

保证所有 $n$ 的总和以及所有 $q$ 的总和均不超过 $10^6$。

输出格式

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

样例

输入 1

1
4 2 3
abcd
ba
1 2
2 2
3 2

输出 1

1
0
0