#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <map>

#include <cmath>

#include <cstring>

#include <string>

#include <queue>

#include <stack>

#include <cctype>

#include <set>

#define ALL(x) x.begin(),x.end()

#define INS(x) inserter(x,x.begin())

using namespace std;

const int maxn = ;

typedef set<int>Set;

map <Set,int>IDcache;

vector<Set>Setcache;

int ID(Set x){

    if(IDcache.count(x))

        return IDcache[x];

    Setcache.push_back(x);

    return IDcache[x] = Setcache.size()-;

}

int main()

{

#ifndef ONLINE_JUDGE

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

#endif

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

    stack<int>s;

    int t;

    cin >> t;

    while(t--){

    int n;

    cin >> n;

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

        string op;

        cin >> op;

        if(op[] == 'P')

            s.push(ID(Set()));

        else if(op[] == 'D')

            s.push(s.top());

        else{

            Set x1 = Setcache[s.top()];

            s.pop();

            Set x2 = Setcache[s.top()];

            s.pop();

            Set x;

            if(op[] == 'U')

                set_union(ALL(x1),ALL(x2),INS(x)); ///并集

            if(op[] == 'I')

                set_intersection(ALL(x1),ALL(x2),INS(x)); ///交集

            if(op[] == 'A'){

                x = x2;

                x.insert(ID(x1));

            }

            s.push(ID(x));

        }

        cout << Setcache[s.top()].size() << endl;

    }

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

    }

    return ;

}