You've got a string s = s₁s₂... s_|s| of length |s|, consisting of lowercase English letters. There also are q queries, each query is described by two integers l_i, r_i (1 ≤ l_i ≤ r_i ≤ |s|). The answer to the query is the number of substrings of string s[l_i... r_i], which are palindromes.

String s[l... r] = s_ls_l + 1... s_r (1 ≤ l ≤ r ≤ |s|) is a substring of string s = s₁s₂... s_|s|.

String t is called a palindrome, if it reads the same from left to right and from right to left. Formally, if t = t₁t₂... t_|t| = t_|t|t_|t| - 1... t₁.

Input

The first line contains string s (1 ≤ |s| ≤ 5000). The second line contains a single integer q (1 ≤ q ≤ 10⁶) — the number of queries. Next q lines contain the queries. The i-th of these lines contains two space-separated integers l_i, r_i (1 ≤ l_i ≤ r_i ≤ |s|) — the description of the i-th query.

It is guaranteed that the given string consists only of lowercase English letters.

Output

Print q integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.

Note

Consider the fourth query in the first test case. String s[4... 6] = «aba». Its palindrome substrings are: «a», «b», «a», «aba».

Queries for Number of Palindromes

Examples