当前没有测试数据。

Description

给定一个长度为 $n$ 的序列，求 $\gcd\{a_l,...,a_r\}\times \text{mex}\{a_l,...,a_r\}$ 的最大值。

其中 $\text{mex}\{A\}$ 表示集合 $A$ 中最小的未出现的正整数。

Format

Input

多组测试数组。

第一行一个正整数 $t(1\le t\le 100)$ 表示数据组数。

接下来 $t$ 组数据，每组两行，第一行一个正整数 $n(1\le \sum n\le 2\times 10^5)$ 表示序列长度，第二行 $n$ 个正整数表示 $a_i(1\le a_i\le 10^9)$。

Output

输出共 $t$ 行，每行一个正整数表示最大值。

Samples

Note

牛客小白月赛 B

2025 zstu 新生赛 mid