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
f(n) = a_1f(n − 1) + . . . a_df(n − d),
where 1 ≤ d ≤ 3, and a_1, ..., 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 ≤ n ≤ 12), followed by n integers containing the given sequence. Each of the given terms has absolute values at most 1000. 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 100000.