#5253. [2018多省省队联测]制胡窜

对于一个字符串S，我们定义|S|表示S的长度。

接着，我们定义Si表示S中第i个字符，S_L,R表示由S中从左往右数，第L个字符到第R个字符依次连接形成的字符串。

特别的，如果L>R，或者L不属于[1,∣S∣],或者R不属于[1,∣S∣]我们可以认为S_L,R为空串。

给定一个长度为n的仅由数字构成的字符串S，

现在有q次询问，第k次询问会给出S的一个字符串S_l,r,请你求出有多少对(i,j)，满足1<=i<j<=n，i+1<j，

且S_l,r出现在S_i+1,J-1或S_j,n中