TKUDDUS - Taklu Kuddus

Kuddus is a great programmer. He recently solved 100 problems in different OJ's. One day his girlfriend gave him a problem. But he failed to solve that problem and his girlfriend became very angry.

For this reason his girlfriend don’t talk to him. He is losing his hair by thinking of how he can solve the problem. Now kuddus came to you for help. As his friend, you have to help kuddus and save his relation and hair also.

The problem is, you are given a string "S" and a pattern "P". You have to find FS(x, y) that is defined as the maximum number of non-overlapping substring which is equal to the pattern "P" in the substring of S which starts at x and end at y (x and y are 0 based indexes).

Suppose S = "abcdef", P = "cd", and the query is (1, 5), so the substring will be "bcdef" and FS(1, 5) = 1

Input

First line contains an integer T (number of test cases) (1 <= T <= 10) Each case starts with a line containing string S, |S| <= 1000000. The next line contains string P, |P| <= 1000000.

Then an integer q (1 <= q <= 100000). Each of the next q lines will contain a query which is in the form i j , (0 ≤ i ≤ j < length(S)).

Output

For each test case, print the case number in a single line.

Then for each query you have to print a line, value of FS(i, j);

It is guaranteed that the summation of all the queries for each test case will not exceed 200000.

Example

Input:
1
abababc
ab
3
0 6
1 2
0 4

Output:
Case 1:
3
0
2

Added by:Raihat Zaman Neloy
Date:2014-10-16
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-10-20 11:35:54 surayans tiwari(http://bit.ly/1EPzcpv)
please increase the time limit its very difficult to pass it

Last edit: 2014-10-21 12:16:07
2014-10-19 15:21:33 surayans tiwari(http://bit.ly/1EPzcpv)
i am using O(n^2) to solve this question will it work?
2014-10-18 19:10:46 Raihat Zaman Neloy
Everything is now correct.

RE: Alright, thanks for fixing.

Last edit: 2014-10-18 23:44:38
2014-10-18 08:19:37 Jacob Plachta
What are the constraints on |S|, |P|, and q? Also, can you verify that the data is fine?

Last edit: 2014-10-18 06:40:37
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.