说明

小 S 有一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$。他拥有一种炫酷魔法，可以将这个序列划分为连续的 $k$ 段，每一段获得的魔法值为这一段中所有数的最大公因数。

小 S 需要使用恰好一次炫酷魔法，他希望通过选择合适的划分方式，使得这 $k$ 个魔法值的算术平均数尽可能大。请计算最大的可能值。

形式化地，给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \ldots, a_n$，你需要选择一个整数 $k$ $(1 \le k \le n)$，并将整个序列划分为 $k$ 个连续的非空子段：

$$[a_1, \ldots, a_{p_1}],\ [a_{p_1 + 1}, \ldots, a_{p_2}],\ \ldots,\ [a_{p_{k-1} + 1}, \ldots, a_n] $$

其中 $p_0 = 1 \le p_1 < p_2 < \cdots < p_{k-1} < n = p_k$。

最大化：

$$\frac{1}{k} \sum_{i=1}^{k} \gcd(a_{p_{i-1}+1}, a_{p_{i-1}+2}, \ldots, a_{p_i}). $$

输入格式

输入包含多组数据。

首先输入一行一个整数 $T$ ($1 \leq T \leq 10^4$)，表示数据的组数。

对于每组数据，首先输入一行一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$)，表示给定序列的长度。

接下来输入一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^6$)，表示给定的序列。

保证对于一个测试点的所有数据，$n$ 的和不超过 $2 \cdot 10^5$。

输出格式

对于每组数据，输出一行一个实数，表示最大的可能值。

当且仅当你的输出与答案的绝对误差或相对误差不超过 $10^{-4}$ 时，你的答案会被判定为正确。

样例

4
3
6 6 8
5
1 6 12 6 4
2
3 5
1
7

7.000000000000
5.800000000000
4.000000000000
7.000000000000

提示

在第一组数据中，将给定的序列划分为 $[6, 6], [8]$ 是最优的。这两个子段的魔法值分别为 $6$, $8$。所有子段的魔法值的\textbf{算术平均数}为 $7$。

在第二组数据中，可以证明，将给定的序列划分为 $[1], [6], [12], [6], [4]$ 是最优的。