Given a string �S of length �n consisting of lowercase English letters. A partition of �S into three non-empty substrings �1,�2,�3s1,s2,s3 is considered good if and only if �1s1 is the border of �1+�2s1+s2 and �3s3 is the border of �2+�3s2+s3. We say a string �s good if and only if �s is a substring of �S and there exists a good partition of �S into �1,�2,�3s1,s2,s3 such that �2=�s2=s.
Define the value of a string as the number of its good substrings. Two substrings are considered different if and only if the start position is different or the end position is different.
Given a string �T of length �m consisting of lowercase English letters and �q queries. In each query, you are given two integers �,�l,r. You need to calculate the value of �[�⋯�]T[l⋯r].
Each test contains multiple test cases. The first line contains an integer �T (1≤�≤601≤T≤60) denoting the number of test cases.
For each test case, the first line contains three integers �,�,�n,m,q (3≤�≤1063≤n≤106, 1≤�,�≤1061≤m,q≤106).
The second line contains a string �S of length �n.
The third line contains a string �T of length �m.
The next �q lines each contains two integers ��li and ��ri, denoting a query (1≤��≤��≤�1≤li≤ri≤m).
It is guaranteed that ∑�,∑�,∑�∑n,∑m,∑q over all test cases does not exceed 106106.
For each query, output one line with an integer denoting the answer.
Please do not output trailing spaces.
1
7 7 2
abacaba
cabacab
1 4
3 70
2