#P1274. 找规律

找规律

大家一定见过这种题目:给你一些数请找出这些数之间的规律,写出下一个满足该规律的数。

比如:2 5 10 17 26,则可以看出这些数符合n*n+1这个通项公式,则下一个数为37。

这种通项公式不只一个,所以答案是不唯一的。但如果已知了N个数,且已知其通项公式是一个次数小于N的多项式,则答案就唯一确定了。

现在给你一个数列,请找出规律并求出其下一个数为多少?

Input

第一行是一个整数T表示测试数据的组数(T<=20)
每组测试数据的第一行是一个整数N(1<=N<=5)
随后的一行有N个整数,表示该数列已知了的N个整数(这N个整数的值都不大于1000)。

Output

输出符合规律的下一个数

Sample Input

2
2
1 2
5
2 5 10 17 26

Sample Output

</p>
3
37

HINT

Source