Distinct Elegant Substrings

Bob loves strings. He considers a string elegant if it is formed by concatenating two identical non‐empty substrings. In other words, a string \(S\) is elegant if there exists a non-empty string \(P\) such that \(S = PP\). For example, aa, sese, abcabc, baabaa, and abababab are elegant, while ab, aadead, sesese, and abba are not.

Bob has a string \(T = T_1T_2 \cdots T_n\) of length \(n\). He is interested in answering \(q\) queries. In each query you are given two integers \(l\) and \(r\) and must consider the substring \(Q = T[l \cdots r]\) (1-indexed). Your task is to determine the number of essentially different elegant substrings contained in \(Q\). Two elegant substrings are considered the same if their content is identical, regardless of their positions in \(Q\>.

Input Format: The input consists of a string \(T\) (in the first line), followed by a line containing a single integer \(q\) representing the number of queries, and then \(q\) lines each containing two integers \(l\) and \(r\).

Output Format: For each query, output a single integer on a new line representing the number of distinct elegant substrings in the given substring \(Q\).

Note: A substring is considered elegant if its length is even and if the first half is exactly the same as the second half (in \(\LaTeX\): a substring \(S\) of even length \(2k\) is elegant if \(S = P P\) where \(P\) is a string of length \(k\)).

inputFormat

The first line contains the string \(T\). The second line contains an integer \(q\), the number of queries. Each of the next \(q\) lines contains two integers \(l\) and \(r\) (1-indexed) representing a query.

Example:

abababab
3
1 8
1 4
3 5

outputFormat

For each query, output one line containing the number of distinct elegant substrings in \(Q = T[l \cdots r]\).

Example:

3
1
0

sample

abababab
3
1 8
1 4
3 5

3
1
0