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.