Problem Description

Given a sequence $a$ of length $n$, determine whether there exists a sequence $b$ such that:

• $S(a)=S(b)$, where $S(a)$ and $S(b)$ denote the multisets formed by all elements in sequences $a$ and $b$, respectively.
• There does not exist any $1 \le i < n$ such that $\gcd(b_1,\cdots,b_i) = \gcd(b_{i+1},\cdots,b_n)$.

Input Format

This problem contains multiple test cases.

The first line of the input contains a positive integer $t$ ($1 \le t \le 10$), indicating the number of test cases.

For each test case:

The first line contains a positive integer $n$ ($2 \le n \le 2 \times 10^5$), indicating the length of sequence $a$.

The second line contains $n$ positive integers $a_1,a_2,\cdots,a_n$ ($1 \le a_i \le 10^{12}$), representing the sequence $a$.

It is guaranteed that $\sum n \le 2 \times 10^5$.

Output Format

For each test case:

If there exists a sequence $b$ satisfying the conditions, output one line "YES"; otherwise, output one line "NO".

You may output the answer in any letter case. For example, "yEs", "yes", "Yes", and "YES" will all be accepted as correct.

7
4
6 12 24 15
5
2 4 3 9 6
6
2 3 5 4 9 25
4
7 7 14 21
2
10 20
3
6 6 6
5
14 21 22 33 17

YES
YES
NO
NO
YES
NO
YES

Hint

Translated by ChatGPT 5