G. Shareefeh's theory with numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

One day, Shareefeh was sitting with her younger sister Fadia, who was studying number theory to prepare herself for marriage. Shareefeh proudly told her that she was already an expert in number theory (which, of course, made sense — after all, she had managed to meet Abu Shehab's standards).

Fadia found herself stuck on the final problem given to her by Em Zeki. Em Zeki had promised that if Fadia solved this problem, she would IMMEDIATELY find her a husband. The problem was as follows:

Given an array of $$$n$$$ integers, rearrange the array to maximize the sum of the $$$GCD$$$ (greatest common divisor) of every pair of adjacent elements. More formally, rearrange the array to maximize: $$${\sum_{i = 2}^n GCD(a_i , a_{i-1})}$$$

Input

The first line contains a single integer $$$t (1≤t≤10^4)$$$ — the number of test cases. Then, $$$t$$$ test cases follow.

The first line of each test case contains one integer $$$n (2≤n≤2\cdot10^5)$$$ — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_i(1≤a_i≤10)$$$ — the elements of the array.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test case, output the maximum possible sum of the $$$GCD$$$s of adjacent elements after rearranging the given array.

Example
Input
2
3
4 2 8
4
1 5 7 10
Output
6
7
Note