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