# GCD operations SOLUTION GCDOPS

Page Contents

### GCD operations SOLUTION GCDOPS

Consider a sequence [Math Processing Error], where initially, [Math Processing Error] for each valid [Math Processing Error]. You may perform any number of operations on this sequence (including zero). In one operation, you should choose two valid indices [Math Processing Error] and [Math Processing Error], compute the greatest common divisor of [Math Processing Error] and [Math Processing Error] (let’s denote it by [Math Processing Error]), and change both [Math Processing Error] and [Math Processing Error] to [Math Processing Error].

You are given a sequence [Math Processing Error]. Is it possible to obtain this sequence, i.e. change [Math Processing Error] to [Math Processing Error], using the given operations?

Input

The first line of the input contains a single integer [Math Processing Error] denoting the number of test cases. The description of [Math Processing Error] test cases follows.

The first line of each test case contains a single integer [Math Processing Error].

The second line contains [Math Processing Error] space-separated integers [Math Processing Error].

Output

For each test case, print a single line containing the string “YES” if it is possible to obtain [Math Processing Error] or “NO” if it is impossible.

Constraints

[Math Processing Error]

[Math Processing Error] for each valid [Math Processing Error]

the sum of [Math Processing Error] over all test cases does not exceed [Math Processing Error]

Subtask #1 (10 points): [Math Processing Error]

Subtask #2 (20 points): there is at most one valid index [Math Processing Error] such that [Math Processing Error]

Subtask #3 (70 points): original constraints

Example Input

2

3

1 2 2

4

1 2 3 2

Example Output

NO

YES

Explanation

Example case 1: We cannot make the third element of the sequence [Math Processing Error] become [Math Processing Error].

Example case 2: We can perform one operation with [Math Processing Error], which changes the sequence [Math Processing Error] to [Math Processing Error].