Max Sum with GCD Greater Than One

You are given an array of integers of size \(N\). Your task is to select two distinct elements \(a\) and \(b\) from the array such that their greatest common divisor (\(\gcd(a, b)\)) is greater than 1, and the sum \(a + b\) is maximized. If no such pair exists, output \(-1\).

Input Format: The first line contains an integer \(T\), the number of test cases. For each test case, the first line contains the integer \(N\), and the second line contains \(N\) space-separated integers representing the array elements.

Output Format: For each test case, output a single line with the maximum sum \(a+b\) of any two distinct numbers whose \(\gcd\) is greater than 1. If no valid pair exists, output \(-1\).

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Each test case consists of two lines: the first line has an integer \(N\), and the second line contains \(N\) space-separated integers representing the array.

outputFormat

For each test case, print on a new line the maximum possible sum of two distinct array elements whose \(\gcd\) is greater than one. If such a pair does not exist, print \(-1\).

## sample

1
5
10 15 3 6 9

25

</p>