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 (a1, . . . , an), 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 a1, a2, . . . , an, 1 ≤ ai ≤ 1012. 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 5 30 60 20 20 20 Sample Output 80