Beautiful Array Transformation

You are given an array of positive integers. Your task is to determine if it is possible to obtain a beautiful array by removing at most one element. An array is considered beautiful if the greatest common divisor (GCD) of all its elements is greater than 1. In mathematical terms, an array \(a_1, a_2, \dots, a_n\) is beautiful if \(\gcd(a_1, a_2, \dots, a_n) > 1\).

You need to check whether the given array is beautiful on its own, or if it can become beautiful after removing just one element.

inputFormat

The first line of input contains an integer \(T\) (\(1 \leq T \leq 10^4\)), the number of test cases. For each test case, the input is given in two lines:

• The first line contains an integer \(n\) (the number of elements in the array).
• The second line contains \(n\) space-separated positive integers.

outputFormat

For each test case, output one line containing YES if the array can be transformed into a beautiful array by removing at most one element, or NO otherwise.

## sample

3
3
4 6 8
4
7 5 9 11
5
15 10 5 10 5

YES
NO
YES

</p>