집합 스택 컴퓨터

한 이론가 집단이 숫자가 아니라 집합을 다루는 슈퍼컴퓨터를 만들고 있습니다. 여러분은 그 시제품인 SetStack Alpha의 동작을 시뮬레이션해야 합니다.

이 기계는 집합들을 담는 스택 하나를 가지며, 처음에는 비어 있습니다. 매 연산이 끝날 때마다 스택 맨 위 집합의 원소 개수를 출력합니다. 집합 $S$의 원소 개수(크기)는 $|S|$로 표기합니다.

명령어는 다섯 가지입니다.

• PUSH — 빈 집합 {}를 스택에 넣습니다.
• DUP — 맨 위 집합을 복제합니다(맨 위를 꺼낸 뒤 같은 집합을 두 번 넣습니다).
• UNION — 맨 위 두 집합을 꺼내고, 두 집합의 합집합을 넣습니다.
• INTERSECT — 맨 위 두 집합을 꺼내고, 두 집합의 교집합을 넣습니다.
• ADD — 맨 위 두 집합을 꺼내고, 첫 번째(위쪽) 집합을 두 번째(아래쪽) 집합의 원소 하나로 추가한 결과를 넣습니다.

집합은 다른 집합을 원소로 가질 수 있으며, 완전히 같은 원소들로 이루어진 두 집합은 서로 같은 것으로 봅니다.

예를 들어 스택의 맨 위가 A = { {}, {{}} }이고 그 아래가 B = { {}, {{{}}} }라면 $|A| = 2$, $|B| = 2$입니다. 이때:

• UNION의 결과는 { {}, {{}}, {{{}}} }이고, 출력은 3입니다.
• INTERSECT의 결과는 { {} }이고, 출력은 1입니다.
• ADD의 결과는 { {}, {{{}}}, {{}, {{}}} }이고, 출력은 3입니다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어집니다($0 \le T \le 5$).

각 테스트 케이스의 첫째 줄에는 연산의 개수 $N$이 주어집니다($0 \le N \le 2000$). 이어지는 $N$개의 줄에는 각각 다섯 명령어 중 하나가 주어집니다.

주어진 명령어들을 실행하는 동안 빈 스택에서 원소를 꺼내는 일은 절대 발생하지 않음이 보장됩니다.

각 연산마다 한 줄에 정수 하나를 출력합니다. 이 값은 해당 명령을 실행한 뒤 스택 맨 위 집합의 원소 개수입니다.

각 테스트 케이스가 끝날 때마다 ***(별표 세 개)만 있는 줄을 출력합니다.