A. Период подстроки

Для каждого запроса $(l, r)$ найдите наименьшую длину $d$, при которой подстрока $s[l..r]$ является строкой длины $d$, выписанной целое число раз.

Иначе говоря: наименьший делитель длины отрезка, который является его периодом.

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

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

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

Для каждого запроса выведите наименьшую длину повторяющегося блока.