A substring of a string S is another string \(S^{d}\) 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 \ne y\)), or there exists such i (\(1 \le i \le min(|x|, |y|\))), that \(x_i \lt y_i\), and for any j (\(1 \le j \lt i\)) \(x_j = y_j\). 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 \le |S|, Q \le 2 \times 10^5\)

\(1 \le L \le R \le |S|\)