题目描述

在本题中，定义一个字符串 $s$ 的 $border$ 为 $s$ 的一个非 $s$ 本身的子串 $t$，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。$border$ 可以为空串。

定义一个字符串 $s$ 的前缀 $x$ 为字符串 $|s_1s_2...s_x|$，本题字符串下标从1开始。

今天的 $Susan$ 想研究一下 $border$

给定一个长度为 $n$ 的字符串 $s$，共有 $q$ 次询问，每次询问给定两个正整数 $x$，$y$，表示询问 $s$ 的前缀 $x$ 长度不超过 $y$ 的最长 $border$ 长度。

输入格式

第一行一个字符串。

第二行一个整数 $q$ 表示询问数

接下来 $q$ 行，每行两个整数 $x$，$y$，表示一次询问

输出格式

共 $q$ 行，每行一个整数，表示询问答案。

样例 #1

样例输入 #1

aaabaaa
3
5 1
7 2
4 4

样例输出 #1

1
2
0

提示

对于50%的数据:

$1\le n,q\le 5\times{10}^3$

对于80%的数据:

$1\le n,q\le 2\times{10}^5$

对于100%的数据:

$1\le n,q\le 2\times{10}^6$

$1\le y\le x\le n$

保证字符集为26个小写英文字母。

样例解释：

第一个询问的前缀是 $aaaba$，$border$ 有 $"","a"$，长度不超过1的最长 $border$ 是 $"a"$

第二个询问的前缀是 $aaabaaa$，$border$ 有 $"","a","aa","aaa"$，长度不超过2的最长 $border$ 是 $"aa"$

第三个询问的前缀是 $aaab$，$border$ 有 $""$，长度不超过4的最长 $border$ 是 $""$。