A String Puzzle

Jonathan knows many fun things from the big world. Today he gave Mavis the following problem. He probably knows it from some informatics olympiad, or maybe from somewhere else.

You have a string and a pointer that initially points to the first character. Two operations are available.

1. Append the character at the current position to the end of the answer, provided that this position's character has not been taken before. Taking it leaves the original character in its position.
2. Move the pointer one character to the right. If the current character is the last one, the pointer goes back to the first character of the string.

After some number of operations, all characters must be taken, and the characters of the answer string must be sorted in non-decreasing order.

For example, with the string hello, you can perform these operations:

1. Second operation. Move the pointer to the character <<e>>.
2. First operation. Take the character <<e>>.
3. Second operation. Move the pointer to <<l>>.
4. Second operation. The pointer is at <<l>>.
5. Second operation. Move the pointer to <<o>>.
6. Second operation. The pointer now points to the first character of the string, <<h>>.
7. First operation. Take <<h>>. The answer string is <<eh>>.
8. Second operation. The pointer is at <<e>>, which is already taken.
9. Second operation.
10. First operation. The answer is <<ehl>>.
11. Second operation.
12. First operation. The answer is <<ehll>>.
13. Second operation.
14. First operation. The answer is <<ehllo>>.

In total, there are $5$ operations of the first type and $9$ operations of the second type.

You need to solve a slightly modified version of this problem in the general case.

The first line contains a string $s$ ($1 \le |s| \le 10^5$) made of lowercase Latin letters. The second line contains the number of queries $m$ ($1 \le m \le 10^5$). Each of the next $m$ lines contains two integers $l_i$ and $r_i$, the bounds of a query.

For each query, print the number of second-type operations needed to solve the problem on the substring of $s$ from position $l_i$ to position $r_i$, inclusive.