Definition

A correct bracket sequence is a string from which the empty string can be obtained by repeating the following $0$ or more times: choose a contiguous substring () and delete it. Also, two characters deleted in a single operation of this process are said to be in a bracket correspondence.

Problem Statement

You are given a correct bracket sequence $S$.

The fairy Chawanmushi-kun is on a character of this bracket sequence. Chawanmushi-kun can move between characters by consuming stamina. When at the $i$-th character of the string $(1\le i \le |S|)$, one of the following moves is possible.

• If $1< i$, consume $1$ stamina and move to the $i-1$-th character.
• If $i< |S|$, consume $1$ stamina and move to the $i+1$-th character.
• If the $i$-th character and the $j$-th character are in a bracket correspondence, move to the $j$-th character without consuming stamina (consuming $0$ stamina).

You are given $Q$ queries. Each query gives integers $l,r$ satisfying $1\le l, r \le |S|$. Find the minimum stamina Chawanmushi-kun must consume to start from the $l$-th character and reach the $r$-th character.

Constraints

• $2 \le |S| \le 2\times 10^{5}$
• $1 \le Q \le 2\times 10^5$
• For each query, $1 \le l, r \le |S|,\ l\neq r$
• $S$ is a correct bracket sequence
• $Q,l,r$ are integers

Input

The input is given from standard input in the following format.

$S$
$Q$
$\rm{query}_1$
$\rm{query}_2$
$\vdots$
$\rm{query}_Q$

Each query is given in the following format.

$l\ r$

Output

Output $Q$ lines. On the $i$-th line, output the minimum stamina Chawanmushi-kun must consume to start from the $l$-th character and reach the $r$-th character in the $i$-th query.

Sample

()((())())
5
2 7
1 10
5 6
1 5
3 9

2
1
0
3
1

((()())(()())(()()))
8
10 20
12 13
6 17
16 18
19 3
14 1
15 6
18 14

3
1
4
1
3
1
4
1