Migrated from Lutece 3064 interval max border

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

给定字符串 $S$，你需要回答 $q$ 次询问，每次询问给定一个区间，求 $S$ 在该区间的子串的最长 border 长度。

Border 的定义：若一个串 $t$ 同时是串 $s$ 的前缀和后缀，则 $t$ 被称为 $s$ 的 border。

Input

第一行一个字符串 $S$。

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

随后的 $q$ 行，每行两个数 $l,r$，表示询问的区间。字符串中字符的下标从 $1$ 开始。

Output

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

Samples

abbabbaa
3
1 8
1 7
2 7

1
4
3

Constraints

$1\le l\le r\le |S|\le 2\times 10^5$ $1\le q\le 2\times 10^5$

Resources

2023 UESTC ICPC Training for String