题目描述

我们知道 Fibonacci 数组通项函数定义如下：

1. F(1)=1
2. F(2)=2
3. F(N)=F(N-1)+F(N-2) 当 N > 2

现在给你 M 个各不相同的正整数 $A_1$, $A_2$, ..., $A_M$，问你能不能找到一 个正整数 S 使得：

F(S) = F($A_1$) + F($A_2$) + ... + F($A_M$)

输入格式

第一行输入一个整数 T，表示有 T 组测试数据。

对于每一组测试数据，第一行 是一个正整数 M，第二行是 M 个正整数 $A_1$, $A_2$, ..., $A_M$ 。

数据范围

0 < M < 10000

0 < $A_i$ < 1000000

输出格式

输出有 T 行，每一行对应一组测试数据。对于每组测试数据，如果能找到满足 的 S, 则输出 S，否则输出-1。

样例

2
2
4 5
3
4 5 6

6
-1