Description

在某次培训中，带师兄讲到了\(kmp\)算法，并给出了一道裸题：
给出一个字符串\(S\)，有\(Q\)次询问，每次询问给出求\(S[1,r]\)的不等于自身的最长公共前后缀长度。其中\(S[1,r]\)表示\(S\)中第\(1\)个字符到第\(r\)个字符拼接而成的连续子串。
但是有的人就是看错了，看成了求\(S[l,r]\)的不等于自身的最长公共前后缀长度。其中\(S[l,r]\)表示\(S\)中第\(l\)个字符到第\(r\)个字符拼接而成的连续子串。
带师兄笑了：“这样也是可以写的，试试看吧。”
接下来是一些补充定义：如果一个字符串某个前缀与某个后缀相同，那么这个前缀就被称为该字符串的公共前后缀。很明显，任何字符串的最长公共前后缀都是它自己，所以本题中我们将这种情况排除。空串是任何非空字符串的公共前后缀，其长度为\(0\)。

Format

Input

每个测试点仅包含一组输入数据。
第一行一个字符串表示\(S\)，\(S\)的长度不超过\(200000\)且仅包含小写英文字母。
第二行一个正整数\(Q(1<=Q<=200000)\)，表示询问个数。
接下来\(Q\)行，每行两个用空格隔开的正整数\(l,r(1<=l<=r<=S的长度)\)。

Output

输出\(Q\)行，按照输入顺序，对于每组询问输出一行一个整数，表示对应的不等于自身的最长公共前后缀长度。

Sample 1

Input

aabaaba
3
1 5 
2 7
3 6

Output

2
3
1

Limitation

4s, 1GB for each test case.

Source

wbs