양의 정수 $n$개로 이루어진 배열 $a$가 주어진다.

배열의 원소를 원하는 순서로 재배열한다. 재배열한 배열이 $b_1,b_2,\ldots,b_n$이라면, 그 값은

$$\operatorname{lcm}(b_1,b_2)+\operatorname{lcm}(b_2,b_3)+\cdots+\operatorname{lcm}(b_{n-1},b_n),$$

즉, 서로 인접한 모든 원소 쌍의 최소공배수의 합이다.

$a$를 재배열하는 모든 방법 중에서 가능한 최댓값을 구하라.

입력

첫 번째 줄에 테스트 케이스의 개수인 정수 $t$ ($1\le t\le10$)가 주어진다.

각 테스트 케이스의 첫 번째 줄에 배열의 원소 개수인 정수 $n$ ($1\le n\le100\,000$)이 주어진다.

두 번째 줄에 정수 $n$개 $a_1,a_2,\ldots,a_n$ ($1\le a_i\le7$)이 주어진다.

모든 테스트 케이스에 걸친 $n$의 합은 $100\,000$ 이하임이 보장된다.

출력

각 테스트 케이스마다 가능한 최댓값을 나타내는 정수 하나를 출력한다.

예제

입력 1

1
2
5 2

출력 1

10

입력 2

1
6
2 2 2 3 3 3

출력 2

30