어떤 길이가 양의 정수인 수열은 잘생긴 GCD 라는 값을 가질 수 있다. 잘생긴 GCD란 그 수열의 모든 원소들의 최대공약수에 수열의 길이를 곱한 값으로 정의된다.

당신의 임무는 수열이 주어질 때(a₁, ... , a_n) 그 수열의 연속된 부분수열들의 잘생긴 GCD 중 가장 큰 값을 구하는 것이다.

입력 형식

입력은 여러개의 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수를 의미하는 T 가 주어진다. 각 각의 테스트 케이스들은 두 줄로 구성되는데,  첫 줄은 수열의 크기 n ( 1 ≤ n ≤ 100 000 )이 주어진다. 두 번째 줄은 수열 a₁, a₂, ... , a_n 이 하나의 공백을 사이에 두고 주어지고 수열의 값은 1 이상 1,000,000,000,000 이하의 값을 가진다.

출력 형식

각 각의 테스트 케이스에서 주어지는 수열의 연속 된 부분수열 중 잘생긴 GCD의 값이 가장 큰 수열의 잘생긴 GCD를 출력한다.

예제 입력

1
5
30 60 20 20 20

예제 출력

80