자동 매매

한 증권사가 자동 매매를 탐지하려고 한다. 특정 알고리즘은 같은 매매 순서를 나중에 그대로 다시 반복한다고 여겨진다. 증권사는 함께 거래될 가능성이 높은 26개의 핵심 종목을 정했고, 일련의 거래를 알파벳 문자열로 기록했다. 각 문자는 종목을 나타내며, 대문자는 매수, 소문자는 매도를 의미한다.

문자열의 두 시작 위치가 주어질 때, 각 시작 위치의 거래를 순서의 첫 거래로 포함하여, 두 위치에서 동일하게 이어지는 가장 긴 거래 순서의 길이를 구하는 프로그램을 작성하여라.

입력에는 여러 개의 테스트 케이스가 있다. 각 테스트 케이스의 첫 줄에는 대문자와 소문자 알파벳으로만 이루어진 문자열 $s$가 주어진다 ($1 \le |s| \le 100{,}000$). 다음 줄에는 질의의 개수를 나타내는 정수 $q$가 주어진다 ($1 \le q \le 100{,}000$). 이어지는 $q$개의 줄에는 각각 두 정수 $i$와 $j$가 주어지며, 이는 문자열에서 0-기반 위치 두 곳을 의미한다 ($0 \le i < j < |s|$).

입력의 끝은 오직 별표(*) 하나만 있는 줄로 표시된다.

각 질의에 대해, 위치 $i$에서 시작하는 거래 순서와 위치 $j$에서 시작하는 거래 순서가 동일하게 이어지는 최대 길이를 정수 하나로 출력한다. 공백은 출력하지 않으며, 출력 줄 사이에 빈 줄을 넣지 않는다.