Problem Description

度度熊很喜欢数组！！

我们称一个整数数组为稳定的，若且唯若其同时符合以下两个条件：

1. 数组里面的元素都是非负整数。
2. 数组里面最大的元素跟最小的元素的差值不超过 $1$。

举例而言，$[1, 2, 1, 2]$ 是稳定的，而 $[-1, 0, -1]$ 跟 $[1, 2, 3]$ 都不是。

现在，定义一个在整数数组进行的操作：

* 选择数组中两个不同的元素 $a$ 以及 $b$，将 $a$ 减去 $2$，以及将 $b$ 加上 $1$。

举例而言，$[1, 2, 3]$ 经过一次操作后，有可能变为 $[-1, 2, 4]$ 或 $[2, 2, 1]$。

现在给定一个整数数组，在任意进行操作后，请问在所有可能达到的稳定数组中，拥有最大的『数组中的最小值』的那些数组，此值是多少呢？

Input

输入的第一行有一个正整数 $T$，代表接下来有几组测试数据。

对于每组测试数据：
第一行有一个正整数 $N$。
接下来的一行有 $N$ 个非负整数 $x_i$，代表给定的数组。

* $1 \le N \le 3 \times 10^5$
* $0 \le x_i \le 10^8$
* $1 \le T \le 18$
* 至多 $1$ 组测试数据中的 $N > 30000$

Output

对于每一组测试数据，请依序各自在一行内输出一个整数，代表可能到达的平衡状态中最大的『数组中的最小值』，如果无法达成平衡状态，则输出 $-1$。

2
3
1 2 4
2
0 100000000

2
33333333