B. Общий префикс двух суффиксов

Дана строка $s$ и запросы: какой длины наибольший общий префикс у суффиксов, начинающихся в позициях $i$ и $j$.

В первой строке - строка $s$ ($1 \le \lvert s \rvert \le 10^5$) из строчных латинских букв.

Во второй - число запросов $q$ ($1 \le q \le 10^5$).

В следующих $q$ строках - пары $i$, $j$ ($1 \le i, j \le \lvert s \rvert$).

Для каждого запроса выведите длину наибольшего общего префикса суффиксов, начинающихся в позициях $i$ и $j$.