对于一个字符串 S,我们定义 ∣S∣ 表示 S 的长度。
接着,我们定义 Si 表示 S 中第 i 个字符,SL,R 表示由 S 中从左往右数,第 L 个字符到第 R 个字符依次连接形成的字符串。特别的,如果 L>R ,或者 L<[1,∣S∣], 或者 R<[1,∣S∣] 我们可以认为 SL,R 为空串。
给定一个长度为 n 的仅由数字构成的字符串 S,现在有 q 次询问,第 k 次询问会给出 S 的一个字符串 Sl,r ,请你求出有多少对 (i,j),满足 1≤i<j≤n,i+1<j,且 Sl,r 出现在 S1,i 中或 Si+1,j−1 中或 Sj,n 中。