关键观察

设进行的总操作次数为 k。则：

• 总和变化：每次操作总和加 2m，故 sum(b) = 2mk，必须有 sum(b) 为偶数，且 2m | sum(b)。
• 每个位置被加的次数为 x_i = b_i / m（必须为非负整数），且 ∑x_i = 2k 为偶数。
• 可行性的图论刻画：每次操作相当于在两个点间连一条边，x_i 为度数。允许多重边、禁止自环。存在这样的多重图的充要条件是 2·max(x_i) ≤ ∑x_i。 将其按 m 约去，得到与 m 无关的必要充分条件：
• 2·max(b_i) ≤ ∑b_i。

题目内容

Tk 有一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$}。初始时，数组中所有元素 $a_i$ 均为 $0$ 。

Tk 想通过以下操作将数组 $a$ 变为给定的数组 $b$ 。

• 选择两个不同的下标 $i,j$，将 $a_i$ 变为 $a_i+m$ ，同时将 $a_j$ 变为 $a_j+m$ 。

问有多少满足条件的正整数 $m$ 能使得最终得到的数组为 $b$ 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^3)$ ，代表数据组数。每组测试数据描述如下：

第一行输入一个整数 $n(2≤n≤2×10^5)$ ，代表数据长度。

第二行输入 $n$ 个正整数 $b_1,b_2,...,b_n(1≤b_i≤10^9)$ ，代表目标数组 $b$ 的各元素。

除此之外。保证单个测试文件中所有 $n$ 的和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，新起一行，输出一个整数，表示满足条件的正整数 $m$ 的个数。

样例1

输入

2
3
2 4 6
2
3 5

输出

2
0