Distinct Substrings Query

Given a lowercase string (S) of length (n), process (m) queries. Each query specifies two integers (L) and (R) and asks: How many essentially different non-empty substrings does the substring (S[L \ldots R]) have?

Note: Two strings (a) and (b) are considered the same if and only if (|a| = |b|) and for every (i) in ([1, |a|]), (a_i = b_i).

inputFormat

The first line contains a string (S) consisting of only lowercase letters.
The second line contains an integer (m) denoting the number of queries.
Each of the next (m) lines contains two integers (L) and (R) describing a query.

outputFormat

For each query, output one integer denoting the number of essentially different non-empty substrings in the substring (S[L \ldots R]).

sample

abc
3
1 1
1 2
1 3

1
3
6