Megumin, a talent explosion magic archwizard, spends a lot of time studying explosion magic spells. For two magic spells A and B, she found that she can combine them together to create a powerful magic spell. Moreover, if the last k characters of A matches the first k characters of B, they can be merged to obtain a more powerful spell. Refer to homework for more examples.
Soon Megumin finds magic spell A too long and wants to shorten it to some substring A'. A substring is a contiguous sequence of characters within a string, specified with two indexes. For example, let A="yyyabcabdab", some substrings of A may be:
A[3...10]="abcabdab" (start from index 3 , end with index 10)
A[0...2]="yyy" (start from index 0 , end with index 2)
Given substring A' please tell her how many ways there are to merge A' with B.
Implementation Hints
Use strlen() to retrieve length of a string with caution. Remember to #include <string.h>
Estimating running time: recall that:
How to estimate the running time of your code?
A usual computer can run 109 basic operations (such as +, -, &, |) in 1 second. Although this depends on the judging server, this number serves as a good estimation for the running time of your code. Try to figure out how much operations your code needs to execute to finish all the computations (since not all operations in your code are basic operations, another estimate criterion is 108 operations (+, -, *, /, =, ...) in 1 second)!
(Maybe useless hint) Draw some examples on paper; observe them; think carefully what you can store to speed up your program.
Notes on Sample IO
Given A="yyyabcabdab", B="abcabd"
For the first substring A'=A[3…10]="abcabdab", possible ways of merging:
A' = abcabdab, B = abcabd 1) ........abcabd 2) ......abcabd
Therefore output 2
For the second substring A'=A[2…8]="yabcabd", possible ways of merging:
A' = yabcabd, B = abcabd 1) .......abcabd 2) .abcabd
Therefore output 2
For the third substring A'= A[2…7]="yabcab", possible ways of merging:
A' = yabcab, B = abcabd 1) .......abcabd 2) ....abcabd 3) .abcabd
Therefore output 3
The first line is an integer T, meaning that the input has T test data. Each test data contains multiple lines.
The first line of each data are two magic spells A and B, where they only contain lower case alphabets (a-z). The second line is an integer Q. In the following Q lines, each contains a substring A' specified with two integers L and R -- the start index and end index of substring of A.
For all test cases:
1 <= T <= 10
0 <= L <= R < |A|
For test case 1-3:
1 <= Q, |A|, |B| <= 100
For test case 4-5:
1 <= Q, |A|, |B| <= 2000
For test case 6:
1 <= Q <= 106
1 <= |A|, |B| <= 2000
For each substring A', output number of ways to merge A' with B in a single line. Remember to add '\n' in the end.