Sereja has a bracket sequence $*s*_{1}, *s*_{2}, ..., *s*_{*n*}$, or, in other words, a string $*s*$ of length $*n*$, consisting of characters "(" and ")".

Sereja needs to answer $*m*$ queries, each of them is described by two integers $*l*_{*i*}, *r*_{*i*}$ $(1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *n*)$. The answer to the $*i*$-th query is the length of the maximum correct bracket subsequence of sequence $*s*_{*l*_{*i*}}, *s*_{*l*_{*i*} + 1}, ..., *s*_{*r*_{*i*}}$. Help Sereja answer all queries.

You can find the definitions for a subsequence and a correct bracket sequence in the notes.

Input

The first line contains a sequence of characters $*s*_{1}, *s*_{2}, ..., *s*_{*n*}$ $(1 ≤ *n* ≤ 10^{6})$ without any spaces. Each character is either a "(" or a ")". The second line contains integer $*m*$ $(1 ≤ *m* ≤ 10^{5})$ — the number of queries. Each of the next $*m*$ lines contains a pair of integers. The $*i*$-th line contains integers $*l*_{*i*}, *r*_{*i*}$ $(1 ≤ *l*_{*i*} ≤ *r*_{*i*} ≤ *n*)$ — the description of the $*i*$-th query.

Output

Print the answer to each question on a single line. Print the answers in the order they go in the input.

Note

A subsequence of length $|*x*|$ of string $*s* = *s*_{1}*s*_{2}... *s*_{|*s*|}$ (where $|*s*|$ is the length of string $*s*$) is string $*x* = *s*_{*k*_{1}}*s*_{*k*_{2}}... *s*_{*k*_{|*x*|}}$ $(1 ≤ *k*_{1} < *k*_{2} < ... < *k*_{|*x*|} ≤ |*s*|)$.

A correct bracket sequence is a bracket sequence that can be transformed into a correct aryphmetic expression by inserting characters "1" and "+" between the characters of the string. For example, bracket sequences "()()", "(())" are correct (the resulting expressions "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

For the third query required sequence will be «()».

For the fourth query required sequence will be «()(())(())».