度度熊的字符串课堂开始了！要以像度度熊一样的天才为目标，努力奋斗哦！
为了检验你是否具备不听课的资质，度度熊准备了一个只包含大写英文字母的字符串 $A[1,n] = a_1 a_2 \cdots a_n$，接下来他会向你提出 $q$ 个问题 $(l,r)$，你需要回答字符串 $A[l,r] = a_l a_{l+1} \cdots a_r$ 内有多少个非空子串是 $A[l,r]$ 的所有非空子串中字典序最小的。这里的非空子串是字符串中由至少一个位置连续的字符组成的子序列，两个子串是不同的当且仅当这两个子串内容不完全相同或者出现在不同的位置。
记 $|S|$ 为字符串 $S$ 的长度，对于两个字符串 $S$ 和 $T$ ，定义 $S$ 的字典序比 $T$ 小，当且仅当存在非负整数 $k(\leq \min(|S|,|T|))$ 使得 $S$ 的前 $k$ 个字符与 $T$ 的前 $k$ 个字符对应相同，并且要么满足 $|S| = k$ 且 $|T| > k$，要么满足 $k < \min(|S|,|T|)$ 且 $S$ 的第 $k+1$ 个字符比 $T$ 的第 $k+1$ 个字符小。例如 "AA" 的字典序比 "AAA" 小，"AB" 的字典序比 "BA" 小。