Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3001

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.

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
Source: ZOJ Monthly, June 2008
Submit    Status