Sereja and Brackets

Source: Codeforces

Version: Phuoc Hung OJ Extended

You are given a bracket string $S$ of length $N$ consisting only of ( and ). For every query $[l,r]$, find the maximum length of a correct bracket subsequence of $S_lS_{l+1}\ldots S_r$.

A correct bracket sequence matches every opening bracket with a later closing bracket and every bracket belongs to exactly one pair.

Input

The first line contains $S$, with $1\le N\le 10^6$.

The second line contains $Q$.

Each of the next $Q$ lines contains $l,r$.

Output

For every query, print the maximum correct bracket subsequence length.

Subtasks

• Subtask 1 — 20%: $1\le N,Q\le 50$.
• Subtask 2 — 30%: $1\le N\le 5000$, $1\le Q\le 5000$.
• Subtask 3 — 50%: $1\le N\le 10^6$, $1\le Q\le 10^5$.

Examples

Input

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

Output

0
0
2
10
4
6
6

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.