J. Widely Known Problem

Problem Description

Given a string $s$ of length $n$ consisting of lowercase English letters. You are given $m$ patterns, where the $i$-th pattern is $s[l_i \dots r_i]$ (indices of $s$ start from $1$). Now, there are $q$ queries, and each query provides $[L_i, R_i]$. For each query, you need to find how many $j$ that the $j$-th pattern occurs in $s[L_i \dots R_i]$.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 10$) - the number of test cases. Description of the test cases follows. The first line of each test case contains three integer $n, m, q$ ($1\leq n\leq 5\times 10^5$, $1\leq m,q\leq 10^6$). The second line contains a string $s$ of length $n$. Each of the following $m$ lines contains two integers $l_i, r_i$ ($1 \le l_i \le r_i \le n$). Each of the following $q$ lines contains two integers $L_i, R_i$ ($1 \le L_i \le R_i \le n$). It's guaranteed that $\sum n \leq 9\times10^5$, $\sum m,\sum q\leq 2\times 10^6$.

Output

For each query, print one integer - the number of patterns occur in the given substring.

Sample Input

2
5 2 2
abaab
3 4
4 5
2 4
1 5
3 2 3
aba
1 2
3 3
1 2
2 3
1 3

Sample Output

1
2
2
1
2

Source

2023“钉耙编程”中国大学生算法设计超级联赛（7）