eolymp
bolt
Try our new interface for solving problems
Problems

IQ Test

IQ Test

Time limit 2 seconds
Memory limit 64 MiB

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 1d3, 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 data

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 (8n12), 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 data

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.

Examples

Input example #1
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
Output example #1
34
1
256
Source 2013 Rocky Mountain Regional ACM Contest