Time Limit Exceeded

While solving problems, you have probably seen a "Time Limit Exceeded" message. It happens for many reasons, but most often when the time complexity of the submitted code exceeds the maximum the problem allows.

In this problem, let's deepen our understanding of time complexity so we run into fewer time-limit errors. Given a piece of source code, compute its time complexity.

Analyzing real code directly is hard, so we use the following simplified model. Assume a program consists of only four instructions:

• basic : a basic operation such as arithmetic or an assignment
• loop : the start of a loop
• endloop : the end of a loop
• endprogram : the end of the program

Analysis follows these rules:

• Only the four instructions above appear in a program.
• Every loop takes exactly one argument and pairs with the first endloop encountered after it to form one loop.
• A loop argument is x, y, or a positive integer. x and y are constants that never change during execution. The loop repeats that many times.
• If a loop contains no basic at all, it is a meaningless loop that terminates immediately regardless of its argument (it contributes nothing to the execution count).
• If a loop contains several basic instructions, you may treat it as containing just one.
• Executing one basic takes constant time.

The time complexity is the number of basic executions expressed as a function of x and y, then simplified with Big-O notation.

Big-O is defined as follows: if you can choose positive constants $c$ and $d$ such that $c \cdot g \le f \le d \cdot g$ holds for every input at least $1$, then the Big-O of $f$ is $O(g)$. Informally, all constant factors can be dropped.

For example, the Big-O of $4x^3$ is $x^3$. Also, when a higher-degree term is present, any lower-degree term can be removed entirely: the Big-O of $x^3 + x^2$ is $x^3$, and of $x^2 + 7$ is $x^2$.

However, when different variables are mixed and a term cannot be guaranteed smaller than the others, every such term must be kept. For example, the Big-O of $x^2y + y^2x + xy + x^2$ is $x^2y + y^2x$, and the Big-O of $x^2 + 17xy + y^2$ is $x^2 + y^2$.

The first line contains the number of test cases $K$. Each test case (program) is separated by a blank line.

Each program consists only of the four instructions described above, and exactly one endprogram appears below the outermost loop.

There is exactly one space between loop and its argument; apart from that, no extra whitespace or other characters appear in a program. Loops are nested at most $50$ levels deep.

For each test case, first print Data Set K: (where $K$ is the 1-based test case number), then print the time complexity of that program.

Print the terms in order of decreasing degree of x; when two terms have the same degree of x, print the one with the higher degree of y first.

Abbreviate each term as much as possible: print xy instead of x^1y^1, and x instead of x^1y^0. If the complexity is constant, print 1; if basic never executes, print 0. Join multiple terms with +.

Print one blank line between consecutive test cases.