팰린드롬과 쿼리 2

소문자로 이루어진 문자열 $S$가 주어진다. 다음 쿼리를 차례대로 처리하는 프로그램을 작성하시오.

• index len: $S$의 index번째 문자에서 시작하는 팰린드롬 부분 문자열 가운데 길이가 len 이상인 것의 개수를 출력한다.

팰린드롬은 앞에서부터 읽어도 뒤에서부터 읽어도 같은 문자열이다. 길이가 0인 문자열도 팰린드롬이다. 따라서 len이 0이면 index에서 시작하는 길이 0인 부분 문자열 하나도 개수에 포함한다.

첫째 줄에 문자열 $S$가 주어진다. $S$의 길이는 100,000을 넘지 않으며, $S$는 알파벳 소문자로만 이루어져 있다.

둘째 줄에 쿼리의 개수 $M$이 주어진다. ($1 \le M \le 100{,}000$)

셋째 줄부터 $M$개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 각 쿼리는 두 정수 index와 len으로 이루어진다. ($0 \le index < |S|$, $0 \le len \le 100{,}000$)

문자열의 인덱스는 0부터 시작한다.

각 쿼리의 답을 입력으로 주어진 순서대로 한 줄에 하나씩 출력한다.