定義

正しい括弧列をある文字列であって、連続部分文字列 () を選び、それを削除することを $0$ 回以上繰り返して空文字列が得られるものとします。また、この操作において一回の操作で消される二文字を、括弧の対応関係にある文字とします。

問題文

ある正しい括弧列 $S$ が与えられます。

妖精の茶碗蒸しくんはこの括弧列の文字の上にいます。茶碗蒸しくんは、体力を消費することで文字の間を移動することができます。文字列の $i$ 文字目 $(1\le i \le |S|)$ にいるとき、以下のいずれかの移動が可能です。

• $1< i$ ならば、体力を $1$ 消費して $i-1$ 文字目へ移動する。
• $i< |S|$ ならば、体力を $1$ 消費して $i+1$ 文字目へ移動する。
• $i$ 文字目と $j$ 文字目が括弧の対応関係にあるならば、体力を消費せずに（体力を $0$ 消費して） $j$ 文字目へ移動する。

$Q$ 個のクエリが与えられます。各クエリでは $1\le l, r \le |S|$ を満たす整数 $l,r$ が与えられるので、茶碗蒸し君が $l$ 文字目からスタートして $r$ 文字目に到達するために必要な最小の消費体力を求めてください。

制約

• $2 \le |S| \le 2\times 10^{5}$
• $1 \le Q \le 2\times 10^5$
• 各クエリに対して $1 \le l, r \le |S|,\ l\neq r$
• $S$ は正しい括弧列
• $Q,l,r$ は整数

入力

入力は以下の形式で標準入力から与えられます。

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

各クエリは以下の形式で与えられます。

$l\ r$

出力

$Q$ 行出力してください。$i$ 行目には $i$ 番目のクエリにおいて、茶碗蒸し君が $l$ 文字目からスタートして $r$ 文字目に到達するために必要な最小の消費体力を出力してください。

サンプル

()((())())
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