405238: GYM101856 B Breaking the Curse

Egypt has finally qualified to the World Cup 2018 after 28 years. It was almost a curse that has been broken. The main factor of this curse was the goal of Abdelghany in the World Cup 1990. Abdelghany has been talking over and over again about this goal that Egyptians started to regret that they have even qualified to that World Cup. Now, since Egypt has made it to the World Cup, lots have said that the curse is over, but of course Abdelghany disagrees. The curse is about someone scoring for Egypt there after him, not only participating. Hence, all Egyptians are praying day and night for any player to score in the 2018 World Cup.

Of course all the hopes are for Egypt’s star Salah to score in the World Cup. Egyptians are interested in knowing the probability that Salah will score in the World Cup and end this curse. Egyptian Scientists decided to calculate this probability for the benefit of the country and the sanity of its people. They encapsulated Salah’s traits, like DNA, personality and quality in a string s₁ and did the same for Abdelghany in a string s₂. Now, they will study the similarity of these two strings in order to calculate the probability of Salah scoring in the World Cup, like Abdelghany. They are making some experiments initially in order to be sure and they want your help, by answering q queries each consisting of two integers L and R; in each query you should find the number of intervals [i, j] (inclusive) where L ≤ i ≤ j ≤ R and s₁[i... j] is a substring of s₂.

The first line of the input contains a single integer 1 ≤ T ≤ 50 the number of test cases. Each test case begins with two lines, the first line is s₁ and the second line is s₂. The two lines are followed by a line containing a single integer q the number of queries, then followed by q lines each containing two space separated integers L, R the values of the query; where the strings s₁, s₂ consist of lower case English characters, 1 ≤ |s₁|, |s₂|, q ≤ 75·10³.

For each test case output a line displaying the case number, followed by q lines each containing a single integer which is the answer to the corresponding query.

2
bbc
abb
4
1 3
1 2
2 3
3 3
hadafkaselalaam
kas
1
1 10

Case 1:
3
3
1
0
Case 2:
8