String Sorting

You'll be given a string $s = s_1s_2.....s_n$ of length $n$ consisting of lowercase English letters and $q$ queries. In each query you'll be given two integers $l$ and $r$, you've to report the minimum number of operations you need to make in order to sort the substring $s_ls_{l+1}.....s_r$. In one operation you can take two adjacent indices and swap the characters.

Input

First line of input contains the string $s$ ($1≤|s|≤10^6$).

Second line of input contains the number of queries $q$ ($1≤q≤10^6$). Next $q$ lines contain two integer $l$, $r$ ($1≤l≤r≤|s|$).

Output

For each query output one integer, the minimum number of operations you need to make.

Sample

Input	Output
bcab 3 1 2 2 3 1 4	0 1 3

Note that, you just have to answer how many operation it takes to sort the substring, you are not making any operation in the string. So the original string doesn't change over queries.