C. Просто массив
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a_1, a_2, \dots, a_n$$$, в котором все $$$a_i$$$ — целые и больше $$$0$$$.

За одну операцию вы можете выбрать две различные позиции $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le n$$$). Если $$$gcd(a_i, a_j)$$$ равен минимуму всего массива $$$a$$$, то вы можете поменять местами $$$a_i$$$ и $$$a_j$$$. $$$gcd(x, y)$$$ означает наибольших общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

Вам нужно сделать массив $$$a$$$ неубывающим, используя заданную операцию произвольное количество раз (возможно, ни разу). Определите, возможно ли это.

Массив $$$a$$$ — неубывающий, тогда и только тогда, когда $$$a_1 \le a_2 \le \ldots \le a_n$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина массива $$$a$$$.

Во второй строке каждого набора заданы $$$n$$$ положительных целых чисел $$$a_1, a_2, \ldots a_n$$$ ($$$1 \le a_i \le 10^9$$$) — сам массив.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора, выведите «YES», если возможно сделать массив $$$a$$$ неубывающим, используя описанную выше операцию, или «NO» в противном случае.

Пример
Входные данные
4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4
Выходные данные
YES
YES
YES
NO
Примечание

В первом и третьем наборах, массив уже неубывающий.

Во втором наборе, мы можем сначала свапнуть $$$a_1$$$ и $$$a_3$$$, а потом $$$a_1$$$ и $$$a_5$$$, и получим неубывающий массив.

В четвертом наборе, невозможно сделать массив неубывающим, используя заданную операцию.