Lexicographical Substring Comparison

Little Y, a university student, is researching string problems. In his study, he considered the following definitions for a string s[1:n]:

• A substring s[l:r] (with 1 ≤ l ≤ r ≤ n) is defined as the string formed by concatenating s[l], s[l+1], …, s[r] in order.
• The reverse of a string, denoted by R(s), is defined as s[n], s[n-1], …, s[1] concatenated in order.
• For two strings of equal length, a[1:n] and b[1:n], we say that a is lexicographically smaller than b if and only if there exists an index 1 \leq i \leq n such that for all 1 \leq j < i we have a[j] = b[j], and a[i] < b[i].

Based on these definitions, Little Y has come up with the following problem:

You are given a string s[1:n] of length n and q queries. Each query gives two parameters i and r. For each query, count the number of positive integers l (with 1 \leq l \leq r and such that i+2l-1 \leq n) that satisfy the condition:

[ s[i : i+l-1] < R(s[i+l : i+2l-1]) ]

Here, s[i : i+l-1] denotes the substring of s from index i to i+l-1, and R(s[i+l : i+2l-1]) is the reverse of the substring from index i+l to i+2l-1 (both substrings are of length l). The lexicographical comparison is defined as above.

Your task is to answer all queries.

inputFormat

The input consists of:

1. A line containing the string s (the string is 1-indexed).
2. A line containing an integer q, the number of queries.
3. q lines, each containing two integers i and r separated by a space.

Note: It is guaranteed that for every valid l considered, the indices i, i+l-1, and i+2l-1 are within the bounds of the string.

outputFormat

For each query, output a single line containing the number of valid l that satisfy the condition.

sample

abacaba
2
1 2
2 1

1
0