Migrated from Lutece 3280 City of Stars

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

Tags: 后缀自动机，LCT

在一个星光璀璨的夜晚，Emma 站在城市的高处，仰望着无尽的星空。耳边回荡着一首悠扬的旋律，她的思绪随着音乐的起伏而飘荡。

Emma 发现夜空中的星星们排列成一排，而连续排列的星星们又组成了一个个星群。

星群可以很大，包含所有夜空中的星星，也可以很小，只包含一颗星星。

她想知道，假如星星的种类可以用小写字母来表示，那么第 $l$ 颗到第 $r$ 颗星星中，有多少种不同的星群。

Input

第一行是一个字符串 $S$，夜空中星星的种类 。

第二行是一个整数 $q$ 表示询问的数量。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$，表示一个区间。

Output

对于每一个询问，输出一个整数，表示在区间 $[l,r]$ 内不同的星群的数量。

Samples

abaa
3
1 2
2 3
3 4

3
3
2

Constraints

$|S|\leq 10^5,q\leq 10^5$

Note

如果夜空中的星星为 $aba$

那么不同的星群有 $a,b,ab,ba,aba$

Resources

2024 UESTC ICPC Training for String