Maximizing the Sum via Prime Factor Replacement

You are given an array (B) of (M) integers. For each integer (n), you may choose to replace it with one of its prime factors, or leave it unchanged. The task is to compute the maximum possible sum obtained by performing such replacements on every element of the array.

More formally, for every integer (n > 1), let its prime factor set be ({p_1, p_2, \dots, p_k}). The contribution of (n) is defined as (\max{n, p_1, p_2, \dots, p_k}). For (n = 1), the contribution is 1.

You will be given multiple test cases. All input is read from stdin and the output is printed to stdout.

inputFormat

The first line contains an integer (P) denoting the number of test cases. For each test case, the first line contains an integer (M) (the number of elements in the array). The second line contains (M) space-separated integers representing the array (B).

outputFormat

For each test case, output a single integer representing the maximum possible sum by replacing each element of (B) with either itself or one of its prime factors.## sample

2
3
12 15 7
2
23 10

34
33