Магический НОД

Магический НОД непустой последовательности натуральных чисел равен произведению ее длины на наибольший общий делитель всех ее элементов.

По заданной последовательности (a_1, ..., a_n) найдите наибольшее возможное значение Магического НОДа ее подпоследовательности с подряд идущими элементами.

Входные данные

Первая строка содержит количество тестов t. Первая строка каждого теста содержит значение n (1 ≤ n ≤ 100000). Следующая строка содержит последовательность чисел a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^12).

Выходные данные

Для каждого теста вывести в отдельной строке наибольшее возможное значение Магического НОДа подпоследовательности с подряд идущими элементами.

Примеры