Problem Statement

For a string $X = X_1X_2\dots X_{|X|}$ and positive integers $l,r~(1 \leq l \leq r \leq |X|)$, let $X_{l,r} = X_l X_{l+1}\dots X_r$.

You are given a string $S=S_1S_2\dots S_{|S|}$ consisting of A and B. You are given $Q$ queries. For each query, answer the following question:

• Starting from the state $T = S_{l,r}$, find the minimum possible length of a palindrome that can be obtained by performing the operation "choose one occurrence of AB that appears as a contiguous substring in $T$ and delete it" zero or more times. If no palindrome can be obtained regardless of how the operation is performed, output -1.

Constraints

• $1 \leq |S| \leq 4 \times 10^5$
• $1 \leq Q \leq 5 \times 10^4$
• $1 \leq l \leq r \leq |S|$
• $S$ is a string consisting of A and B.
• $Q,l,r$ are integers.

Input

The input is given from Standard Input in the following format:

S
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

$\mathrm{Query}_q$ represents the $q$-th query and is given in the following format:

l r

Output

Output $Q$ lines. The $q$-th line should contain the answer for $\mathrm{Query}_q$.