Handsome GCD

Time limit5sMemory limit128 MB

Summary

Find the maximum of gcd times length over all contiguous subarrays of the given sequence.

Level: Medium7 of 10
Topics: Number theory
Solved: No attempts yet

Problem

Every sequence whose length is a positive integer has a value called its handsome GCD. The handsome GCD is the greatest common divisor of all elements of the sequence, multiplied by the length of the sequence.

Given a sequence $a_1, a_2, \dots, a_n$ , find the largest handsome GCD among all contiguous subsequences of that sequence.

Input

The input holds several test cases. The first line contains $T$ , the number of test cases.

Each test case takes two lines. The first line contains the length of the sequence $n$ ( $1 \le n \le 100\,000$ ). The second line contains the elements $a_1, a_2, \dots, a_n$ separated by single spaces. Every element satisfies $1 \le a_i \le 10^{12}$ .

Output

For each test case, print on one line the largest handsome GCD over all contiguous subsequences of the given sequence. The answer is a single integer and it is unique.

Examples1

Example 1
Input
```
1
5
30 60 20 20 20
```
Expected output
```
80
```