D. Magic Books
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Marisa has $$$n$$$ magic books placed on a shelf, all of them volumes from the same collection. Each book has an associated number within the collection. Initially, the book in position $$$i$$$ on the shelf is volume number $$$a_i$$$ of the collection, for $$$1\le i \le n$$$.

Since the magic books are very delicate, they can only be moved using the following operation. Two indices $$$1\le i \lt j \le n$$$ are chosen such that the volume numbers of the books in positions $$$i,i+1,\dots,j$$$ on the shelf are pairwise coprime$$$^{\text{∗}}$$$; and the order of the books in positions $$$i,i+1,\dots,j$$$ is reversed. That is, the book in position $$$i+r$$$ would move to position $$$j-r$$$ for each $$$0\le r \le j-i$$$.

Help Marisa decide if she can sort the books on the shelf using this operation as many times as she wants. We say that the books on the shelf are sorted if the volume numbers form a non-decreasing sequence from the book in position $$$1$$$ to the book in position $$$n$$$.

$$$^{\text{∗}}$$$We recall that two integers are coprime if their greatest common divisor is 1. We say that several numbers are pairwise coprime if any pair of them is coprime.

Input

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

Each test case starts with an integer $$$n$$$, the number of books on the shelf.

The next line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, where $$$a_i$$$ is the volume number of the book initially in position $$$i$$$. Note that $$$a_1,a_2,\dots,a_n$$$ do not have to be pairwise distinct.

Output

For each test case, print on one line the word "YES" when it is possible to sort the books, and the word "NO" when it is not possible.

Example
Input
4
4
6 1 1 1
5
5 4 3 2 1
5
5 2 3 4 1
4
2 2 6 3
Output
SI
NO
SI
NO
Note
  • $$$1 \le T \le 1000$$$
  • $$$1 \le n \le 10^5$$$
  • $$$1\le a_1, a_2, \dots, a_n \le 10^6$$$
  • The sum of $$$n$$$ over all cases will not exceed $$$2\cdot 10^5$$$.