Return to the Sky

In this problem, each person is assigned a lowercase letter ('a' to 'z') as an ID. People are arranged in a line, and some of them will be grouped together to "Return to the Sky". A contiguous group (or interval) of people can return to the sky if the characters in that interval can be rearranged into a palindrome. In other words, a substring is considered valid if its characters can be permuted to form a palindrome.

You are given a string s of lowercase letters representing the IDs of people in line. Then, there are m queries. Each query gives two integers l and r (1-indexed) representing a segment of the string. For each query, you need to count how many of its subintervals (i.e. contiguous substrings of s[l...r]) can be rearranged to form a palindrome.

A well-known fact is that a string can be rearranged into a palindrome if and only if at most one character appears an odd number of times. Equivalently, after counting the frequency of each letter, at most one frequency is odd.

For example, if s = "aba" and a query is l=1, r=3, then the valid subintervals are: "a" (position 1), "b" (position 2), "a" (position 3) and "aba" (positions 1 to 3). Thus, the answer is 4 for this query.

inputFormat

The first line contains a non-empty string s consisting of lowercase letters.

The second line contains an integer m, the number of queries.

Each of the next m lines contains two integers l and r (1-indexed), representing a query which asks for the number of subintervals of the segment s[l...r] that can be rearranged into a palindrome.

outputFormat

For each query, output a single integer on a new line, indicating the count of subintervals within s[l...r] that can be rearranged to form a palindrome.

sample

aba
2
1 2
1 3

0
4