#include<stdio.h>
 
int t,n;
char s[2000005];
 
int main()
{
    scanf("%d",&t);
    while(t--)
	{
        scanf("%d",&n);
        scanf("%s",s);
        int cnt1=0,ans=0;
        int i; 
        for(i=0;i<n;i++)
		{
			switch(s[i])
			{
			case'0':
				if(cnt1>0)
				{
	                ans++;
	                cnt1--;
	            }
	            break;
			case'1':
				cnt1++;
				break;
			default:
				ans++;
			}
        }
        printf("%d\n",ans+cnt1/2);
    }
    return 0;
}

#include<stdio.h>
 
char a[2000005];
int t,x,mod;
int n=0;
 
int main()
{
    scanf("%s",a);
    scanf("%d",&t);
    mod=strlen(a);
    while(t--)
	{
        char op;
        scanf("%s",&op);
        scanf("%d",&x);
        if(op=='A')
		{
            int tmp=x+n;
            printf("%c\n",a[(tmp-1)%mod]);
        }
        else
		{
            n=(n+x+mod)%mod;    
        }
    }
    return 0;
}