Square Cutting

Two players take turns cutting one rectangular sheet of paper. The long side of the sheet has length $L$ and the short side has length $W$.

On a turn, a player cuts the largest square that fits in the rectangle that is left. In a rectangle whose short side is $W$, that square has side $W$. The player cuts one or more squares of that size, every square cut in the turn has the same size, and what remains after the cut must be a single rectangle. The player who cuts the paper with nothing left over wins.

A game is recorded as $L\ W\ r\ a_1\ a_2\ \dots\ a_r$, where $r$ is the number of turns and $a_i$ is the number of squares cut on turn $i$. For example, on a sheet with long side 5 and short side 2, the first player cuts two squares of side 2 and leaves a $2 \times 1$ rectangle, then the second player cuts two squares of side 1 and the game ends. The record of that game is 5 2 2 2 2.

A storage fault erased the first two numbers, $L$ and $W$, from every record. Recover $L$ from the surviving $r$ and $a_1$ through $a_r$. When several values of $L$ are possible, answer with the smallest one.

The first line contains the number of records $M$.

Each of the next $M$ lines holds one record. The line starts with the number of turns $r$, followed by $r$ integers $a_1$ through $a_r$ separated by spaces.

• $1 \le M \le 20$
• $1 \le r \le 50$
• $1 \le a_i \le 100$
• Every record comes from a game that can actually be played, so $a_r \ge 2$ whenever $r \ge 2$.
• The original sheet satisfies $1 \le W \le L \le 10^{100}$.

Print $M$ lines. On line $i$, print the smallest long side $L$ among the rectangles that produce record $i$.