Suffix Tree Node Count via Suffix Automaton

Given a string (P) of length (n) and (m) queries, each query provides two integers (l) and (r). For each query, consider the substring (S = P[l, r]) (using 1-indexed positions). You are required to compute the number of nodes in the suffix tree constructed from (S), with the root node excluded. Alternatively, if you are not familiar with suffix trees, you can interpret the problem as follows: take the reverse of (S) (i.e. (T = \text{reverse}(S))), build the suffix automaton for (T), and report the number of states excluding the initial state. That is, the answer for each query is [ \text{answer} = |\text{SuffixAutomaton}(T)| - 1. ]

Note that the input string (P) consists of characters and the queries use 1-indexed positions.

inputFormat

The first line contains the string (P).\nThe second line contains an integer (m), the number of queries.\nEach of the next (m) lines contains two integers (l) and (r), representing the range of the substring (P[l, r]) (1-indexed).

outputFormat

For each query, output a single line containing the required number described above, which is the number of nodes in the suffix tree of (P[l, r]) (excluding the root) or equivalently the number of states in the suffix automaton for (\text{reverse}(P[l, r])) minus 1.

sample

ababa
3
1 2
2 5
1 5

2
4
5