ZOJ Problem Set - 3001
Tom forgot his password! Fortunately he is self-knowledge to write some hints for the password before. But he is too busy to solve the hints, so he asked you, a good friend of him to help him.
For a given sequence a, a, ..., a[m], you can find a polynomial whose degree is no more than m-1, f(i) = a[i],(1<=i<=m). f(m+1) is the password of Tom. Your task is to find out the password by the given sequence.
There are multiple cases in the input.
There is only one integer on the line 1, indicating the number of the cases.
Each case begins with one integer m (1 <= m <= 200), which is the amount of sequence. Then there are m integers, a, a, ..., a[m].
For each test, print the password in a single line.
3 3 2 4 6 3 1 4 9 6 1 1 1 1 1 1
8 16 1
Author: ZHANG, Rui
Source: ZOJ Monthly, June 2008