P16962 [SCCPC 2026] Exchange the Rest of Your Life

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)$.

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$.

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.

Translated by ChatGPT 5