The SetStack Computer

A group of theorists is building a supercomputer that operates on sets instead of numbers. Your job is to simulate its prototype, the SetStack Alpha.

The machine keeps a single stack of sets, which starts out empty. After every operation it prints the cardinality of the set currently on top of the stack. The cardinality of a set $S$, written $|S|$, is the number of elements it contains.

There are five commands:

• PUSH — push the empty set {} onto the stack.
• DUP — duplicate the top set (pop it, then push it back twice).
• UNION — pop the top two sets and push their union.
• INTERSECT — pop the top two sets and push their intersection.
• ADD — pop the top two sets, insert the first (upper) set as a single element of the second (lower) set, and push the result.

Sets may contain other sets as elements, and two sets with exactly the same elements are considered equal.

As an illustration, suppose the top of the stack is A = { {}, {{}} } and the set just below it is B = { {}, {{{}}} }. Then $|A| = 2$ and $|B| = 2$, and:

• UNION produces { {}, {{}}, {{{}}} }, so the output is 3.
• INTERSECT produces { {} }, so the output is 1.
• ADD produces { {}, {{{}}}, {{}, {{}}} }, so the output is 3.

The first line contains an integer $T$ with $0 \le T \le 5$: the number of test cases.

Each test case begins with a line containing the number of operations $N$ with $0 \le N \le 2000$. The next $N$ lines each contain one of the five commands.

It is guaranteed that the machine can execute the whole command sequence without ever popping from an empty stack.

For each operation, print a single line containing one integer: the cardinality of the set on top of the stack after that command has executed.

After each test case, print a line containing *** (three asterisks).