该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景+描述+输入格式+输出格式

小海有1个字符串(下标从1开始),他知道每个字符串都有字串,只要给定一组r,l

现在他想知道自己字符串给定r,l时的字符串的所有子串中,有多少种不一样的(不包括空串)

先输入S,下一行再输入一个数m,表示询问的组数

接下来m行,每行一个l,r,么一个对应一个输出

输出是输出m行,每行一个数,表示有多少种不一样的

样例

abacabc
3
1 3
2 3
3 5

5
3
5

$S.size()\le10^5 , m\le2\times10^5$