8603: Striking String Problem

NIO is given two strings $S$ and $T$ consisting of lowercase letters, an integer $k$ and 2k integers li, ri (1≤i≤k)。
Define U=S[l1,r1]+S[l2,r2]+⋯+S[lk,rk]. He has $q$ queries, each described by two integers $x$ and $y$. For a query, he wants to know the number of times that $T$ appears in U[x,y]. Help him!

Print q lines. The i-th of them contains a single integer - the answer to the i-th query.

abaaba
abaa
8 10
1 6
4 6
3 6
2 4
5 6
2 2
5 5
1 4
1 24
21 24
1 15
1 23
6 6
4 7
1 8
8 16
16 23
7 20

5
1
3
4
0
1
2
1
0
2