Migrated from Lutece 3063 count substrings

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一个字符串 $S$，请你回答 $q$ 组询问，每组询问为求 $S$ 的一个区间内的本质不同的非空子串个数。

两个子串本质不同，当且仅当这两个子串的内部构造不同。

Input

第一行一个字符串 $S$ 和一个整数 $q$。

接下来 $q$ 行，每行两个整数 $l,r$，表示询问的区间。字符串中字符的下标从 $1$ 开始。

Output

对于每组询问，输出一行一个整数表示区间本质不同的非空子串个数。

Samples

abcca
5
3 4
2 2
2 5
2 4
1 4

2
1
9
5
9

Constraints

$1\leq l\leq r\leq |S|\le 10^5$ $1\le q\leq 10^5$

Resources

2023 UESTC ICPC Training for String