The \textit{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 (\textbf{a_1}, ..., \textbf{a_n}), find the largest possible Magical GCD of its connected subsequence. \InputFile The first line of input contains the number of test cases \textbf{t}. The descriptions of the test cases follow: The description of each test case starts with a line containing a single integer \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{100000}). The next line contains the sequence \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_n} (\textbf{1 }≤ \textbf{a_i} ≤ \textbf{10^12}). \OutputFile For each test case output one line containing a single integer: the largest Magical GCD of a connected subsequence of the input sequence.