# Magical GCD

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.

## Input

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}$.

## Output

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

Sample Input 1 | Sample Output 1 |
---|---|

1 5 30 60 20 20 20 |
80 |