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₁, ..., a_n), find the largest possible Magical GCD of its connected subsequence.

입력

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 ≤ n ≤ 100 000. The next line contains the sequence a₁, a₂, ..., a_n, 1 ≤ a_i ≤ 10¹².

출력

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

1
5
30 60 20 20 20

80