IQ Test

IQ tests often ask this kind of question.

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

For (1, 2, 3, 5, 8, 13, 21) the answer is easy: this is the Fibonacci sequence, so the next term is 34.

The next term is an integer, but a great many polynomials pass through the given terms, so a great many answers are possible. This problem accepts only a sequence that satisfies a recurrence of the form

$f(n) = a_1 f(n-1) + a_2 f(n-2) + \cdots + a_d f(n-d)$

where $1 \le d \le 3$ and $a_1, \dots, a_d$ are integers. When several such recurrences fit the sequence, the one with the smallest $d$ gives the answer.

The input holds several test cases. The first line has the number of test cases, which is at most 500.

Each test case is one line. The first number on the line is the length $n$ ($8 \le n \le 12$) of the sequence, followed by the $n$ integers of the sequence separated by spaces. Each integer has absolute value at most 1000. Every sequence in the input satisfies at least one recurrence of the form above, and for the $d$ of the answering recurrence the first $d$ numbers are not 0.

For each test case, print the next term on its own line. Its absolute value is at most 100,000.