#include <iostream>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <vector>
#define Range(x) x.begin(),x.end()
#define Insert(x) inserter(x,x.begin())

using namespace std;
typedef set<int> Set;
map<Set,int> IDhash;
vector<Set> Sethash;
int t,n=0;

//some code from Rujia's algorithm book
int ID(Set x){
    if(IDhash.count(x))return IDhash[x];

    Sethash.push_back(x);

    return IDhash[x] = Sethash.size()-1;
}

int main () {

  cin>>t;
  while(t--){

    stack<int> s;
    cin>>n;

    for(;n>0;n--){

        string op;
        cin>>op;

        if(op[0]=='P')
        s.push(ID(Set()));
        else if(op[0]=='D')
        s.push(s.top());

        else{
            Set s1 = Sethash[s.top()];s.pop();
            Set s2 = Sethash[s.top()];s.pop();
            Set x;
            if(op[0]=='U') set_union (Range(s1),Range(s2),Insert(x));
            if(op[0]=='I') set_intersection(Range(s1),Range(s2),Insert(x));
            if(op[0]=='A')
            {
                x = s2;
                x.insert(ID(s1));
            }
            s.push(ID(x));
        }
        cout<<Sethash[s.top()].size()<<endl;

    }
    cout<<"***"<<endl;

  }
  system("PAUSE");
}