Uniform Array Transformation

You are given an array of integers. In one operation, you can replace the array by performing an operation (details hidden).

Your task is to determine whether it is possible to transform the array so that all its elements become equal. The transformation is possible if and only if either the array is already uniform or the greatest common divisor (GCD) of all its elements is 1.

Recall that the GCD of an array \(a_1,a_2,\dots,a_n\) is defined as \(\gcd(a_1, a_2, \dots, a_n)\). In particular, if \(\gcd(a_1, a_2, \dots, a_n)=1\), then it is possible to perform a sequence of operations to eventually make all elements equal.

Read the input from stdin and write the result to stdout.

inputFormat

The first line contains an integer \(T\) \( (1 \le T \le 10^4)\), the number of test cases.

Each test case consists of two lines:

• The first line contains a single integer \(n\) \( (1 \le n \le 10^5)\), the number of elements in the array.
• The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) \( (1 \le a_i \le 10^9)\).

The sum of \(n\) over all test cases does not exceed \(10^6\).

outputFormat

For each test case, output a single line containing YES if it is possible to transform the array into a uniform array, or NO otherwise.

## sample

3
4
1 2 1 2
3
2 4 8
2
1 1

YES
NO
YES

</p>