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

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 ≤ n ≤ 100000). The next line contains the sequence a_1, a_2, ..., a_n (1 ≤ a_i ≤ 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.

Examples