\includegraphics{https://static.e-olymp.com/content/9c/9c4ac0e7ef449881bcf95965b55a8000f539ddaa.jpg} 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 \textbf{1, 1, 2, 3, 5, 8, 13, 21} you may recognize this as the Fibonacci numbers and write down \textbf{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 \textbf{f(n) = a_1f(n − 1) + . . . a_df(n − d)}, where \textbf{1} ≤ \textbf{d} ≤ \textbf{3}, and \textbf{a_1}, ..., \textbf{a_d} are integers. If the sequence satisfies multiple recurrence relations of the type above, we will always prefer one with a smaller \textbf{d}. \InputFile The input consists of multiple test cases. The first line of input is a single integer, not more than \textbf{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 \textbf{n} (\textbf{8} ≤ \textbf{n} ≤ \textbf{12}), followed by \textbf{n} integers containing the given sequence. Each of the given terms has absolute values at most \textbf{1000}. You may also assume that the given sequence satisfies at least one recurrence relation in the form described above. The first \textbf{d} terms in the given sequence are non-zero, for the smallest \textbf{d} for which a recurrence exists. \OutputFile 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 \textbf{100000}.