
67  ZOJ Monthly, June 2008  1006
Tom forgot his password! Fortunately he is selfknowledge 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. Task For a given sequence a[1], a[2], ..., a[m], you can find a polynomial whose degree is no more than m1, 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. Input 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[1], a[2], ..., a[m]. Output For each test, print the password in a single line. Sample Input 3 3 2 4 6 3 1 4 9 6 1 1 1 1 1 1 Sample output 8 16 1 Author: ZHANG, Rui 