問題文

tatesoto 君は以下の問題を考えました。

文字 :, (, ) からなる文字列について考えます。 隣接する 2 文字が以下のいずれかであるとき、その 2 文字を顔文字と呼びます。

• :), (: を笑顔と呼びます。
• :(, ): を悲しい顔と呼びます。

文字列 T に含まれる笑顔（悲しい顔）の個数とは、1 \le i \lt |T| を満たし、T_iT_{i+1} が笑顔（悲しい顔）であるような整数 i の個数を指します。

複数の顔文字が同じ文字を共有している場合も、それぞれ数えることに注意してください。例えば、文字列 (:): には、(:, :), ): が含まれるため、笑顔の個数は 2、悲しい顔の個数は 1 です。

文字列 T が与えられます。 あなたは T に対して、以下の操作を悲しい顔が含まれなくなるまで繰り返します。

• 現在の文字列 T に含まれる悲しい顔を 1 つ選び、その 2 文字を削除する。その後、残った文字を順番を変えずに詰める。

最終的な文字列 T に含まれる笑顔の個数としてあり得る最大値を求めてください。

この問題は soryuusi 君には簡単すぎたので、この問題を基に次のような問題を考えました。

:, (, ) からなる文字列 S と Q 個のクエリが与えられます。 i 番目のクエリでは、整数 L_i,R_i (1\leq L_i \leq R_i \leq |S|) が与えられるので、部分文字列 T = S_{L_i}S_{L_i+1}\cdots S_{R_i} に対する tatesoto 君の問題の答えを求めてください。

soryuusi 君の問題を解いてください。

制約

• S は :, (, ) からなる文字列
• 1\leq |S| \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1\leq L_i \leq R_i \leq |S|
• 入力される数値はすべて整数

入力例 1

(:):(
4
2 5
1 3
3 5
1 5

出力例 1

1
2
0
2

1 つ目のクエリについて、T = :):( です。 T の 3, 4 文字目の :( を削除することで、T = :) となります。 このときの笑顔の個数は 1 個であり、これが最大であることが証明できます。

2 つ目のクエリについて、T = (:) です。 このとき、最初から悲しい顔は含まれず、笑顔の個数は 2 個です。

3 つ目のクエリについて、T = ):( です。 T の 1, 2 文字目の ): を削除することで、T = ( となります。 このときの笑顔の個数は 0 個であり、これが最大であることが証明できます。

4 つ目のクエリについて、T = (:):( です。 T の 4, 5 文字目の :( を削除することで、T = (:) となります。 このときの笑顔の個数は 2 個であり、これが最大であることが証明できます。

入力例 2

::::::::
1
1 8

出力例 2

0

入力例 3

)()):)()))::::(:::):(((::)(():
10
13 22
20 22
16 26
2 21
1 28
7 28
14 18
23 24
3 7
10 16

出力例 3

1
0
3
2
4
4
0
1
0
0