#include <cstring>

 #include <cstdio>

 const int N();

 int n,top,ans;

 char s[N];

 int Presist()

 {

     freopen("shower.in","r",stdin);

     freopen("shower.out","w",stdout);

     scanf("%s",s);    n=strlen(s);

     for(int i=; i<n; ++i)

     {

         if(s[i]=='(') top++;

         else

         {

             if(top<) top++,ans++;

             else top--;

         }

     }

     printf("%d\n",ans+top/);

     return ;

 }

 int Aptal=Presist();

 int main(int argc,char*argv[]){;}

 #include <cstdio>

 inline void read(int &x)

 {

     x=; register char ch=getchar();

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 const int N(1e6+);

 bool not_pri[N],flag;

 long long sum[N];

 int pri[N],cnt,t;

 inline void Prepare()

 {

     register int i,j;

     for(i=; i<=1e6; ++i)

     {

         if(!not_pri[i]) pri[++cnt]=i;

         for(j=; j<=cnt; ++j)

         {

             if(i*pri[j]>1e6) break;

             not_pri[i*pri[j]]=;

             if(i%pri[j]==) break;

         }

     }

     for(i=; i<=cnt; ++i)

         sum[i]=sum[i-]+1ll*pri[i];

 }

 int Presist()

 {

     freopen("diary.in","r",stdin);

     freopen("diary.out","w",stdout);

 //    freopen("1.txt","r",stdin);

     Prepare(); read(t);

     for(register int n,k,i,j; t--; )

     {

         read(n),read(k); flag=;

         for(i=cnt; i>=k; --i)

         {

             j=i-k;

             if(sum[i]-sum[j]<=n)

             {

                 printf("%I64d\n",sum[i]-sum[j]);

                 flag=; break;

             }

         }

         if(flag) puts("-1");

     }

     return ;

 }

 int Aptal=Presist();

 int main(int argc,char**argv){;}

 #include <algorithm>

 #include <cstdio>

 #include <map>

 #define LL long long

 const int mod(1e9+);

 const int N();

 typedef std:: map<std:: pair<LL,LL>, LL> Mm1;

 typedef std:: map<LL,LL> Mm2;

 Mm1 mm1[N];

 Mm2 mm2[N];

 inline void read(LL &x)

 {

     x=; register char ch=getchar();

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 LL a[N],b[N],c[N],d[N],l[N];

 LL F[N],n[N];

 inline LL dis(LL i,LL x,LL y)

 {

     if(x>y) { LL a=x;x=y;y=a;}

     if(x==y) return ;

     Mm1::iterator it=mm1[i].find(std::make_pair(x,y));

     if(it!=mm1[i].end()) return it->second;

     LL na=n[a[i]];

     if(x>=na) return mm1[i][std::make_pair(x,y)]=dis(b[i],x-na,y-na)%mod;

     else if(y<na) return mm1[i][std::make_pair(x,y)]=dis(a[i],x,y)%mod;

     else return mm1[i][std::make_pair(x,y)]=(dis(a[i],x,c[i])+dis(b[i],d[i],y-na)+l[i])%mod;

 }

 inline LL f(LL i,LL j)

 {

     if(!i) return ;

     Mm2:: iterator it=mm2[i].find(j);

     if(it != mm2[i].end()) return it->second;

     LL na=n[a[i]];

     if(j<na) return mm2[i][j]= ( f(a[i],j)+n[b[i]]%mod*

                                  dis(i,j,d[i]+na)%mod+

                                  f(b[i],d[i])) %mod;

     else return mm2[i][j]= ( f(b[i],j-na)+n[a[i]]%mod*

                              dis(i,j,c[i]) %mod+

                              f(a[i],c[i])) %mod;

 }

 int Presist()

 {

     freopen("cloth.in","r",stdin);

     freopen("cloth.out","w",stdout);

     int m; scanf("%d",&m);

     F[]=; n[]=;

     for(int i=; i<=m; ++i)

     {

         read(a[i]),read(b[i]),read(c[i]),read(d[i]),read(l[i]);

         n[i]=n[a[i]]+n[b[i]];    l[i]%=mod;

         LL na=n[a[i]]%mod, nb=n[b[i]]%mod;

         printf("%I64d\n",F[i]=( F[a[i]]+F[b[i]]+

                                 nb*f(a[i],c[i])%mod+

                                 na*f(b[i],d[i])%mod+

                                 na*nb %mod*l[i]%mod)%mod);

     }

     return ;

 }

 int Aptal=Presist();

 int main(int argc,char**argv){;}