P16792 [Lanqiao Cup 2026 National A] Non-Coprime Game

Xiaolan and his friend Xiaoqiao are playing a game about positive integers. At the beginning, there are $n$ positive integers $a_1, a_2, \ldots, a_n$ on the table. Xiaolan moves first, and the two players take turns. In one move, a player needs to choose a number $x$ currently on the table and change it to a smaller positive integer $y$. This change is legal if and only if $1 \le y < x$ and $x$ and $y$ are not coprime. “Not coprime” means the greatest common divisor of the two positive integers is greater than $1$, i.e. $\gcd(x, y) > 1$. For example, for the number $8$, it can be changed to $2, 4, 6$; for the number $15$, it can be changed to $3, 5, 6, 9, 10, 12$. The number $1$ and all prime numbers cannot be changed, because there is no smaller positive integer $y$ that satisfies the conditions. When it is a player’s turn, if they cannot make any legal move, then that player loses the game. It is known that both Xiaolan and Xiaoqiao will use optimal strategies. Now determine whether Xiaolan has a winning strategy for the given initial position.

This problem contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. Then $T$ test cases follow. Each test case consists of two lines: * The first line contains a positive integer $n$, representing the number of initial numbers. * The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$, representing the initial position of the game.

For each test case, output one line. If Xiaolan must win, output `Yes`; otherwise output `No`.

### Sample Explanation For the first test case, Xiaolan can change $100$ to $2$. After that, $1, 3, 2$ can no longer be legally changed. Xiaoqiao has no legal move, so Xiaolan must win. For the second test case, the two numbers are the same. No matter how Xiaolan changes one of them, Xiaoqiao can make the same change to the other one. In the end, Xiaolan will face a position with no legal moves, so Xiaoqiao must win. ### Constraints For $40\%$ of the test cases, $1 \le n \le 10$, $1 \le a_i \le 3000$. For $80\%$ of the test cases, $1 \le n \le 100$, $1 \le a_i \le 20000$. For all test cases, $1 \le T \le 200$, $1 \le n \le 1000$, $1 \le a_i \le 300000$, and the sum of $n$ over all test cases does not exceed $100000$. Translated by ChatGPT 5