A substring of a string S is another string Sd that occurs "in" S. For example, "thebestof" is a substring of "Itwasthebestoftimes". This is not to be confused with subsequence, which is a generalization of substring. For example, "Itwastimes" is a subsequence of "Itwasthebestoftimes", but not a substring.
You are given a string S and Q queries on it. In each query, you will be given two integers L and R. For each query, you need to find the lexicographic rank of the substring between indices L and R among all the substrings of this string.
String x is lexicographically less than string y, if either x is a prefix of y (and x ≠ y), or there exists such i (1 ≤ i ≤ min(|x|, |y|)), that xi < yi, and for any j (1 ≤ j < i) xj = yj. Here a denotes the length of the string a.
There might be some queried substrings which occur more than once in the given string. You should consider the queried substring a as the lexicographically largest among all substrings of S which are equal to a.
Input:
First line of input contains the string S. Next line contains an integer Q, denoting the number of queries. Each of the next Q lines contain 2 integers L and R, the end points of the substring in the corresponding query.
Output:
For each query, output the answer in a new line.
Constraints:
1≤|S|,Q≤2×105
1≤L≤R≤|S|
These are the strings in lexicographic order: [a,a,a,ad,ad,ad,adk,adk,adka,...]
The rank of adk is 8th.