Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
67 - ZOJ Monthly, June 2008 - 1006
Password

Time Limit: 2 Seconds      Memory Limit: 32768 KB

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.

Task

For a given sequence a[1], a[2], ..., 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.

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

Submit    Status