[CERC2013] Magical GCD

题意翻译

有 $T$ 组询问,每次给出 $n$ 个数 $a_i$。 你需要找到这个数组的一个子序列(要求编号连续),使得该序列中所有数的最大公约数和序列长度的乘积最大,并输出这个最大值。

题目描述

The Magical GCD of a nonempty sequence of positive integers is defined as the product of its length and the greatest common divisor of all its elements. Given a sequence $(a_1, \ldots , a_ n)$, find the largest possible Magical GCD of its connected subsequences.

输入输出格式

输入格式


The first line of input contains the number of test cases $T$. The descriptions of the test cases follow: The description of each test case starts with a line containing a single integer $n$, $1 \leq n \leq 100\, 000$. The next line contains the sequence $a_1, a_2 , \ldots , a _ n$, $1 \leq a_ i \leq 10^{12}$.

输出格式


For each test case output one line containing a single integer: the largest Magical GCD of a connected subsequence of the input sequence.

输入输出样例

输入样例 #1

1
5
30 60 20 20 20

输出样例 #1

80

说明

Time limit: 8000 ms, Memory limit: 1048576 kB. Central Europe Regional Contest (CERC) 2013