#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<stack>
#include<vector>
#define F(i,a,b) for (int i=a;i<b;i++)
#define FF(i,a,b) for (int i=a;i<=b;i++)
#define mes(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
#define pb push_back
using namespace std;
const int N=500500,MAX=1000100;

int main()
{
    int t,n,x,flag,tot1,tot2,a[N];
    char str[15];
    deque<int >DQ;
    scanf("%d",&t);
    FF(cas,1,t){
        DQ.clear();
        flag=0;
        tot1=((N>>1)-1),tot2=(N>>1);
        scanf("%d",&n);
        printf("Case #%d:\n",cas);
        while(n--){
            scanf("%s",str);
            if(str[2]==‘S‘){
                scanf("%d",&x);
                if(!flag){
                    if(!x)DQ.push_back(tot1);
                    a[tot1--]=x;
                }else {
                    if(!x)DQ.push_front(tot2);
                    a[tot2++]=x;
                }
            }

            else if(str[1]==‘O‘){
                if(!flag){
                    tot1++;
                    if(!a[tot1])DQ.pop_back();
                }else {
                    tot2--;
                    if(!a[tot2])DQ.pop_front();
                }
            }

            else if(str[0]==‘R‘){
                flag^=1;
            }

            else {
                if(tot2-tot1-1==0)puts("Invalid.");
                else if(DQ.empty()) cout<<((tot2-tot1-1)%2)<<endl;
                else {
                    if(!flag){
                        cout<<((tot2-DQ.front()-1+(tot1+1!=DQ.front()))%2)<<endl;
                    }else {
                        cout<<((DQ.back()-tot1-1+(DQ.back()!=tot2-1))%2)<<endl;
                    }
                }
            }
        }
    }

    return 0;
}