Problem H
IQ Test

In many IQ tests, the following type of questions is often given:

Given the first few terms of an integer sequence, what is the next term?

For example, if you are given the sequence $1, 1, 2, 3, 5, 8, 13, 21$ you may recognize this as the Fibonacci numbers and write down $34$ as the next term.

There is no “correct answer” because the next term can be any integer and still be generated by a polynomial (possibly of a very high degree). In this problem, we are only interested in sequences that satisfy a recurrence relation of the form

where $1 \leq d \leq 3$, and $a_1, \ldots , a_ d$ are integers. If the sequence satisfies multiple recurrence relations of the type above, we will always prefer one with a smaller $d$.

Input

The input consists of multiple test cases. The first line of input is a single integer, not more than $500$, indicating the number of test cases to follow. Each case is specified on one line. Each line contains a number of integers: the number of given terms in the sequence $n$ ($8 \leq n \leq 12$), followed by $n$ integers containing the given sequence. Each of the given terms has absolute values at most $1\, 000$. You may also assume that the given sequence satisfies at least one recurrence relation in the form described above. The first $d$ terms in the given sequence are non-zero, for the smallest $d$ for which a recurrence exists.

Output

For each case, display on a line the next term generated by the recurrence relation selected by the criteria above. You may assume that the next term in the sequence has absolute value at most $100\, 000$.

3
8 1 1 2 3 5 8 13 21
8 1 1 1 1 1 1 1 1
8 1 -2 4 -8 16 -32 64 -128

34
1
256