Tom Sawyer and Huckleberry Finn read a newspaper clipping aloud together. But it so happened that Tom Sawyer began to read from the i-th character, and Huckleberry Finn from the j-th.
How many letters can they read before they find they started from different places, or until they both read to the end?
Input:
The first line contains the string S (1 <= |S| <= 10
5), consisting of lowercase Latin letters - an inscription from a newspaper clipping.
The next line contains a natural number q - the number of requests.
The next q lines contain two natural numbers i and j each - the positions from which Tom Sawyer and Huckleberry Finn start reading, respectively.
Output:
Print q lines, each of which should contain one integer - the number of characters that match when reading substrings starting with the i-th and j-th characters.
Examples:
| Input |
Output |
abacaba
4
15
3 5
4 2
26 |
3
1
0
2 |