Background

upd 2024/5/12 18:14: Added two sets of hack testdata, located in Subtask 1, worth $0$ points.

upd 2024/5/12 21:27: Added one set of hack testdata, located in Subtask 1, worth $0$ points.

Problem Description

Given a sequence $a$ of length $n$.

Define one operation as choosing three integers $x,y,z\in[1,n]$ such that $\gcd(a_x,a_y)=a_z$ and $x,y,z$ are pairwise distinct, then eliminate $a_z$ (that is, in later operations you can no longer choose $a_z$).

Ask whether, after some number of operations, it is possible to eliminate $n-2$ numbers among $a_1\sim a_n$.

Input Format

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case:

The first line contains a positive integer $n$.

The second line contains $n$ positive integers $a_i$.

Output Format

For each test case, output one line containing a string Yes or No.

2
3
1 2 3
3
1 2 4

Yes
No

Hint

Sample Explanation:

• For the first test case, you can eliminate $1$ using $(2,3)$.
• For the second test case, it can be proven that there is no solution.

Constraints

There are $20$ test points in total, and each test point is worth $5$ points.

For $100\%$ of the data, $1\le T\le 10^5$, $2\leq n \leq 10^6$, $2 \le \sum n\le 10^6$, $1\le a_i\le 10^9$.

Translated by ChatGPT 5