In high school mathematics, the elements of a set are often concrete numbers, such as $A = \{1, 2, 3\}$, $B = \{\}$ (the empty set), etc. However, it is important to note that the elements of a set can also be other sets. For example, $C = \{\{\}\}$, which means $C$ has exactly one element—the empty set $B$. Therefore, it is correct to say that $B$ is a subset of $C$ or that $B$ is an element of $C$. The cardinality of a set is the number of elements in the set, generally denoted as $|S|$. The cardinality of the empty set is $0$. In the example above, $|A| = 3$, $|B| = 0$, and $|C| = 1$.

Given the fact that set theory is a foundational theory of modern mathematics, a group of imaginative scientists has begun to build a new type of supercomputer—the Setstack machine Alpha. This machine operates on sets rather than numbers. However, since the completion date of Alpha is far off, the scientists hope you can write a virtual machine for them so they can check whether their prototype design is reasonable.

The storage device of Alpha consists of a single stack, where each unit of the stack can hold one set. Initially, the stack is empty. After each operation, the computer outputs the cardinality of the set located at the top of the stack. Alpha has five different instructions: PUSH, DUP, UNION, INTERSECT, and ADD. Their functions are as follows:

• PUSH: Pushes an empty set $\{\}$ onto the stack.
• DUP: Pops the set from the top of the stack, duplicates it, and pushes both identical sets back onto the stack.
• UNION: Pops the top two sets from the stack, then pushes their union onto the stack.
• INTERSECT: Pops the top two sets from the stack, then pushes their intersection onto the stack.
• ADD: Pops the top two sets from the stack. Let the first one popped be $S$ and the second one popped be $T$. Finally, push $T \cup \{S\}$ onto the stack.

Taking the diagram on the left as an example, the two elements at the top of the virtual machine stack are: $A = \{ \{\}, \{\{\}\} \}$ $B = \{ \{\}, \{\{\{\}\}\} \}$

According to the definition of cardinality, we have $|A| = 2$ and $|B| = 2$. Next: If the UNION operation is selected, the result is $\{\{\}, \{\{\}\}, \{\{\{\}\}\}\}$, output $3$. If the INTERSECT operation is selected, the result is $\{\{\}\}$, output $1$. * If the ADD operation is selected, the result is $\{\{\}, \{\{\{\}\}\}, \{\{\}, \{\{\}\}\}\}$, output $3$.

Input

The first line of the file contains a single integer $n$ ($0 \le n \le 2000$), representing the number of instructions to be executed. This is followed by $n$ lines, each containing one uppercase instruction. We guarantee that each instruction is one of the five mentioned above, and the virtual machine will always be able to execute all instructions correctly.

Output

Output the results of the virtual machine. Each line should contain an integer greater than or equal to $0$, representing the output of the virtual machine after executing the corresponding instruction. Participants should carefully consider the execution efficiency of their programs.

Examples

Input 1

9
PUSH
DUP
ADD
PUSH
ADD
DUP
ADD
DUP
UNION

Output 1

0
0
1
0
1
1
2
2
2

Input 2

5
PUSH
PUSH
ADD
PUSH
INTERSECT

Output 2

0
0
1
0
0

Constraints

For $20\%$ of the data, $n \le 10$. For $100\%$ of the data, $n \le 2000$.