We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. HourRank 1
  3. GCD Groups

GCD Groups

Gukiz has an easy task for you:

You are given an array of even length . We want to split it into two disjoint groups with elements each, so that the Greatest Common Divisor (GCD) of all numbers in each group is greater than . Is this possible?

Note: A disjoint group means that each element of array is located in exactly one group.

Input Format

The first line of the input contains a single integer , denoting the number of test cases.

The first line of each testcase contains one even number : the length of the array in the testcase.

The second line of each testcase contains separated integers , representing array .

Constraints:





Note: The scoring for this problem is binary. You have to pass all the test-cases to get a positive score.

Output Format

For each testcase, print a single line "YES" (without the quotes) if it is possible to make a split with the aforementioned described properties. If it's not possible, print a single line "NO".

Sample Input:

2
6
8 10 24 20 45 30
2
25 1

Sample Output:

YES
NO

Explanation

The number of testcases is .

In the first testcase, we have an array of length 6. We can split the array into 2 sets with elements. One possible way:

     Valid because

    Valid because

There are many other ways to split this.

In the second testcase, we have an array with elements. The only way to split it into groups with sizes is to make 2 groups with 1 element each. So, 1 group will contain the number only, and its GCD will be equal to . So, the answer is "NO".