Xiao Z and Xiao A are playing a card game to compare their hands.

The rules of the game are as follows:

• Before the game starts, the system deals a pile of cards to Xiao Z and a pile of cards to Xiao A (the number of cards in the two piles may be different). Each card has a lowercase letter written on it.
• In each round of the game, Xiao Z and Xiao A simultaneously reveal the top card of their respective piles. If the revealed cards are different, the player with the smaller lowercase letter on their card wins. If the revealed cards are the same, they place the revealed cards at the bottom of their respective piles and continue the game until one player wins.

The system actually deals cards from a massive deck. Specifically, suppose the deck has $n$ cards, $a_1, a_2, \dots, a_n$. The system randomly selects cards from index $l$ to $r$ to deal to a player. In other words, the player's cards from the top of the pile to the bottom are $a_l, a_{l+1}, \dots, a_r$.

Now, Xiao Z and Xiao A are to play $q$ rounds of the game. Xiao Z has learned through some means that in the $i$-th round, the cards dealt to Xiao A are $a_{l_i}, a_{l_i+1}, \dots, a_{r_i}$. Xiao Z wants to know how many possible hands he could have that would allow him to win against Xiao A. Two hands are considered different if and only if the number of cards in the hands is different, or if there exists a position $d$ such that the cards at distance $d$ from the top of the pile are different.

Input

Read the data from standard input.

The first line of input contains a string $a$ consisting only of lowercase letters.

The second line of input contains a positive integer $q$ and an integer $type$, where $type$ indicates the data type.

The next $q$ lines each contain two integers $l_i$ and $r_i$.

Output

Output to standard output.

Output $q$ lines, each containing an integer representing the number of possible hands Xiao Z could have to win against Xiao A.

Examples

Input 1

abbab
5 0
1 3
2 4
3 5
1 4
2 5

Output 1

4
7
6
2
8

Input 2

(input data)

Output 2

(output data)

Input 3

(input data)

Output 3

(output data)

Constraints

For all data, $1 \le l_i \le r_i \le |a| \le 5 \times 10^{5}$ and $1 \le q \le 5 \times 10^{5}$.

The meanings of the data types $type$ are:

• $type=0$: No special restrictions.
• $type=1$: Guaranteed that $\exists 1 \le l' \le r' \le |a|$ such that $a_{l_i,r_i} + a_{l_i,r_i} = a_{l',r'}$.
• $type=2$: Guaranteed that $\forall r'-l' = r_i-l_i+1$, if $a_{l',r'-1} = a_{l_i,r_i}$, then $a_{r'} \neq a_{l_i}$.
• $type=3$: Guaranteed that $\sum r_i-l_i \le 10^5$.

Here, $a_{l,r}$ denotes the substring $a_l a_{l+1} \dots a_r$; the result of $a+b$ is the concatenation of strings $a$ and $b$ in order.