//prepare for coding{{{
#include<bits/stdc++.h>

#define RELEASE
#ifdef RELEASE
#define DB(...) ;
#else
#define FL
#ifdef FL
#define DB(...) fprintf(stderr,__VA_ARGS__)
#else
#define DB printf
#endif
#endif 
#define int long long

const int N=100000,Q=100000,LGN=20;
const int INF=1000000000;

using namespace std;

inline int Read(){
	char c=getchar();
	int res=0;
	bool b=0;
	while(c>'9'||c<'0')
		b=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')
		res=(res<<3)+(res<<1)+c-'0',c=getchar();
	return b?-res:res;
}

inline void ReadS(int &n,bool a[]){
	char c=getchar();
	while(c!='('&&c!=')')
		c=getchar();
	n=0;
	while(c=='('||c==')')
		a[++n]=(c=='('),c=getchar();
}

inline int Min(int a,int b){
	return a>b?b:a;
}

inline int Mod(int x,int mod){
	return ((x-1)%mod+mod)%mod+1;
}

int n,q;
bool a[N+10];
//}}}

//st table{{{
int mn[LGN+10][N+10],tl;
int lg[N+10];
int bs,dj;

inline void ST(){
	lg[1]=0;
	for(int i=2;i<=tl;++i)
		lg[i]=lg[i>>1]+1;
	for(int i=1,s=2;s<=tl;++i,s<<=1)
		for(int j=1;j+s-1<=tl;++j)
			mn[i][j]=Min(mn[i-1][j],mn[i-1][j+(s>>1)]);
	dj=n-2*tl;
	bs=Min(mn[lg[tl]][1],mn[lg[tl]][tl-(1<<lg[tl])+1]);
}

inline int ST_Min(int l,int r){
	int t=lg[r-l+1];
	return Min(mn[t][l],mn[t][r-(1<<t)+1]);
}

inline int Query(int l,int r){
	int tnl=(l+tl-1>0?(l+tl-1)/tl:l/tl),tnr=(r>0?(r-1)/tl:r/tl-1);
	if(tnl==tnr+1)
		return ST_Min(Mod(l,tl),Mod(r,tl))+tnr*dj;
	int a=ST_Min(Mod(l,tl),tl)+(tnl-1)*dj,b=ST_Min(1,Mod(r,tl))+tnr*dj;
	return Min(Min(a,b),tnl==tnr?INF:bs+dj*(dj>0?tnr-1:tnl));
}
//}}}

//solve{{{
inline int Get(int tn,int x){
	return Query(x,x+tn)+x+x+tn;
}

inline int Lower_Bound(int tn,int lim){
	int l=-INF,r=INF-1,ans=INF;
	while(l<=r){
		int mid=(l+r)>>1;
		if(Get(tn,mid)>=lim)
			r=(ans=mid)-1;
		else
			l=mid+1;
	}
	return ans;
}

inline int Upper_Bound(int tn,int lim){
	int l=-INF,r=INF-1,ans=INF;
	while(l<=r){
		int mid=(l+r)>>1;
		if(Get(tn,mid)>lim)
			r=(ans=mid)-1;
		else
			l=mid+1;
	}
	return ans;
}
//}}}

//main{{{
inline void Solve(){
	tl=0;
	ReadS(n,a);
	for(int i=1;i<=n;++i)
		if(a[i])
			++tl,mn[0][tl]=i-1-2*tl;
	ST();
	q=Read();
	for(int i=1;i<=q;++i){
		int tn=Read(),l=Read(),r=Read();
		printf("%lld\n",tl?Upper_Bound(tn,r)-Lower_Bound(tn,l):0);
	}
}

signed main(){
#ifdef FL
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	int T=Read()+1;
	while(--T)
		Solve();
	return 0;
}
//}}}
//《象》曰：泽灭木，大过。君子以独立不惧，遁世无闷。