Sereja has a bracket sequence s1, s2, ..., sn, 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 li, ri (1 ≤ li ≤ ri ≤ n). The answer to the i-th query is the length of the maximum correct bracket subsequence of sequence sli, sli + 1, ..., sri. Help Sereja answer all queries.

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

The first line contains a sequence of characters s1, s2, ..., sn (1 ≤ n ≤ 106) without any spaces. Each character is either a "(" or a ")". The second line contains integer m (1 ≤ m ≤ 105) — the number of queries. Each of the next m lines contains a pair of integers. The i-th line contains integers li, ri (1 ≤ li ≤ ri ≤ n) — the description of the i-th query.

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

A subsequence of length |x| of string s = s1s2... s|s| (where |s| is the length of string s) is string x = sk1sk2... sk|x|(1 ≤ k1 < k2 < ... < 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 «()(())(())».

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define ll long long

#define pi (4*atan(1.0))

#define eps 1e-14

#define bug(x)  cout<<"bug"<<x<<endl;

const int N=1e6+,M=1e7+,inf=1e9+;

const ll INF=1e18+,mod=1e9+;

///   数组大小

char s[N];

struct ans

{

    int x,y,z;

    ans(){}

    ans(int xx,int yy,int zz)

    {

        x=xx;y=yy;z=zz;

    }

};

struct SGT

{

    int LT[N<<],RT[N<<],MT[N<<];

    void pushup(int pos)

    {

        int k=min(LT[pos<<],RT[pos<<|]);

        MT[pos]=MT[pos<<]+MT[pos<<|]+*k;

        LT[pos]=LT[pos<<]+LT[pos<<|]-k;

        RT[pos]=RT[pos<<]+RT[pos<<|]-k;

    }

    void build(int l,int r,int pos)

    {

        if(l==r)

        {

            LT[pos]=;

            RT[pos]=;

            MT[pos]=;

            if(s[l]=='(')

                LT[pos]++;

            else

                RT[pos]++;

            return;

        }

        int mid=(l+r)>>;

        build(l,mid,pos<<);

        build(mid+,r,pos<<|);

        pushup(pos);

    }

    ans query(int L,int R,int l,int r,int pos)

    {

        if(L==l&&r==R)

            return ans(LT[pos],MT[pos],RT[pos]);

        int mid=(l+r)>>;

        if(R<=mid)

            return query(L,R,l,mid,pos<<);

        else if(L>mid)

            return query(L,R,mid+,r,pos<<|);

        else

        {

            ans a=query(L,mid,l,mid,pos<<);

            ans b=query(mid+,R,mid+,r,pos<<|);

            int k=min(a.x,b.z);

            int m=a.y+b.y+*k;

            int l=a.x+b.x-k;

            int r=a.z+b.z-k;

            return ans(l,m,r);

        }

    }

};

SGT tree;

int main()

{

    scanf("%s",s+);

    int x=strlen(s+);

    tree.build(,x,);

    int q;

    scanf("%d",&q);

    while(q--)

    {

        int l,r;

        scanf("%d%d",&l,&r);

        printf("%d\n",tree.query(l,r,,x,).y);

    }

    return ;

}

/*

))(()))))())())))))())((()()))))()))))))))))))

9

26 42

21 22

6 22

7 26

43 46

25 27

32 39

22 40

2 45

*/