Module: 해싱

Problem

Tom Sawyer와 Huckleberry Finn은 함께 큰 소리로 신문 스크랩을 읽습니다. 그러나 Tom Sawyer는 i번째 문자부터 읽기 시작했고 Huckleberry Finn은 j번째 문자부터 읽기 시작했습니다. 
서로 다른 곳에서 시작하거나 둘 다 끝까지 읽을 때까지 얼마나 많은 편지를 읽을 수 있습니까?

입력:
첫 번째 줄에는 문자열 S(1 <= |S| <= 10⁵)가 포함되어 있으며 소문자 라틴 문자로 구성되어 있습니다. 이는 신문에서 발췌한 내용입니다.
다음 줄에는 요청 수인 자연수 q가 포함됩니다.
다음 q 줄에는 각각 Tom Sawyer와 Huckleberry Finn이 읽기 시작하는 위치인 두 개의 자연수 i와 j가 포함됩니다.

출력:
q 줄을 인쇄합니다. 각 줄은 i번째 및 j번째 문자로 시작하는 하위 문자열을 읽을 때 일치하는 문자 수인 하나의 정수를 포함해야 합니다.

예:
  <몸>

입력	출력
아바카바 4 15 3 5 4 2 26	3 1 0 2