题目背景
现在你回来了，需要完成一个任务。
题目描述
给定一个仅由小写英文字母组成的字符串 $s$。
定义 $f(s)$ 为字符串 $s$ 中 不同子串 的数量。
现在你需要处理若干次询问，每次给出两个整数 $l,r$，你需要计算：
$$ f(s[l \dots r]) $$
其中 $s[l \dots r]$ 表示字符串 $s$ 从第 $l$ 个字符到第 $r$ 个字符构成的子串。
一个字符串的子串，指的是字符串中连续的一段字符。
两个子串被认为不同，当且仅当它们的内容不同。
输入格式
第一行一个整数 $T$，表示测试用例组数。
对于每组测试数据：
- 第一行一个字符串 $s$，仅由小写英文字母组成。
- 第二行一个整数 $Q$，表示询问个数。
- 接下来 $Q$ 行，每行两个整数 $l,r$，表示一次询问。
输出格式
对于每组测试数据中的每次询问，输出一行一个整数，表示答案。
输入输出样例 #1
输入 #1
2
bbaba
5
3 4
2 2
2 5
2 4
1 4
baaba
5
3 3
3 4
1 4
3 5
5 5输出1
3
1
7
5
8
1
3
8
5
1数据范围
30%的数据 n<=100,q<=100
70的数据，n<=3000,q<=20000