Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Consider a sequence $A_{1}, A_{2}, \ldots, A_{N}$, where initially, $A_{i} = i$ for each valid $i$. You may perform any number of operations on this sequence (including zero). In one operation, you should choose two valid indices $i$ and $j$, compute the greatest common divisor of $A_{i}$ and $A_{j}$ (let's denote it by $g$), and change both $A_{i}$ and $A_{j}$ to $g$.

You are given a sequence $B_{1}, B_{2}, \ldots, B_{N}$. Is it possible to obtain this sequence, i.e. change $A$ to $B$, using the given operations?

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $B_{1}, B_{2}, \ldots, B_{N}$.

------ Output ------
For each test case, print a single line containing the string "YES" if it is possible to obtain $A = B$ or "NO" if it is impossible.

------ Constraints ------
$1 ≤ N ≤ 10^{4}$
$1 ≤ B_{i} ≤ i$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{5}$

------ Subtasks ------
Subtask #1 (10 points): $N ≤ 4$

Subtask #2 (20 points): there is at most one valid index $p$ such that $B_{p} \neq p$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------
2

3

1 2 2

4

1 2 3 2
----- Sample Output 1 ------
NO

YES
----- explanation 1 ------
Example case 1: We cannot make the third element of the sequence $(1, 2, 3)$ become $2$.

Example case 2: We can perform one operation with $(i, j) = (2, 4)$, which changes the sequence $(1, 2, 3, 4)$ to $(1, 2, 3, 2)$.

见题面

见题面