一家经纪公司对检测自动交易很感兴趣。他们认为某种特定的算法会自我重复；也就是说，它会在稍后的时间进行相同的交易序列。该公司确定了 26 只他们认为可能会协同交易的关键股票，并将一系列交易编码为字母字符串：字母本身表示股票，大写字母表示买入，小写字母表示卖出。他们希望你编写一个程序，对于任意两个起始点，确定从这两个起始点开始（包含起始点本身作为序列的第一笔交易）的最长相同交易序列的长度。

输入格式

输入包含多个测试用例。每个测试用例的第一行是一个字符串 $s$，仅由大写和小写字母组成（$1 \le \text{length}(s) \le 100,000$）。下一行是一个整数 $q$（$1 \le q \le 100,000$），表示查询的数量。接下来的 $q$ 行，每行描述一个查询，包含两个整数 $i$ 和 $j$（$0 \le i < j < \text{length}(s)$），分别代表字符串中两个从零开始的索引位置。输入以仅包含一个星号（'*'）的行结束。

输出格式

对于每个查询，输出一个整数，表示从 $i$ 开始的交易序列与从 $j$ 开始的交易序列相同的最长长度。不要输出空格。输出行之间不要打印任何空行。

样例

输入格式 1

ABABABcABABAbAbab
3
0 2
1 6
0 7
SheSellsSeashellsByTheSeaShore
4
8 22
1 20
8 25
0 1
*

输出格式 1

4
0
5
3
4
1
0