You are given an array $a_1, a_2, \dots, a_n$ where all $a_i$ are integers and greater than $0$.

 In one operation, you can choose two different indices $i$ and $j$ ($1 \le i, j \le n$). If $gcd(a_i, a_j)$ is equal to the minimum element of the whole array $a$, you can swap $a_i$ and $a_j$. $gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

 Now you'd like to make $a$ non-decreasing using the operation any number of times (possibly zero). Determine if you can do this.

 An array $a$ is non-decreasing if and only if $a_1 \le a_2 \le \ldots \le a_n$.


-----Input-----

 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

 The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of array $a$.

 The second line of each test case contains $n$ positive integers $a_1, a_2, \ldots a_n$ ($1 \le a_i \le 10^9$) — the array itself.

 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

 For each test case, output "YES" if it is possible to make the array $a$ non-decreasing using the described operation, or "NO" if it is impossible to do so.


-----Example-----
Input
4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4

Output
YES
YES
YES
NO



-----Note-----

 In the first and third sample, the array is already non-decreasing.

 In the second sample, we can swap $a_1$ and $a_3$ first, and swap $a_1$ and $a_5$ second to make the array non-decreasing.

 In the forth sample, we cannot the array non-decreasing using the operation.

Difficulty: interview

Starter code:

Solutions:
from math import gcd
for _ in range(int(input())):
    n = int(input())
    l = list(map(int,input().split()))
    newList = sorted(l)
    m = newList[0]
    div = newList[0]
    for i in range(n):
        if l[i]!=newList[i]:
            div = gcd(div,l[i])
    if div%m==0:
        print("YES")
    else:
        print("NO")

import sys
from math import gcd

input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    A=[a[i] for i in range(n)]
    A.sort()
    m=min(a)
    check=all(a[i]==A[i] or a[i]%m==0 for i in range(n))
    print("YES" if check else "NO")


t=int(input())
for you in range(t):
    n=int(input())
    l=input().split()
    li=[int(i) for i in l]
    z=min(li)
    l1=[]
    hashimul=dict()
    for i in range(n):
        if(li[i]%z==0):
            l1.append(li[i])
            hashimul[i]=len(l1)-1
    l1.sort()
    lfi=[]
    for i in range(n):
        if(i in hashimul):
            lfi.append(l1[hashimul[i]])
        else:
            lfi.append(li[i])
    poss=1
    for i in range(1,n):
        if(lfi[i]<lfi[i-1]):
            poss=0
            break
    if(poss):
        print("YES")
    else:
        print("NO")

for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    b = a.copy()
    b.sort()
    impflag = 0
    arr = []
    val = min(a)
    for i in range(n):
        if a[i] != b[i]:
            arr.append(b[i])
    for i in arr:
        if i%val != 0:
            impflag = 1
            break
    if impflag == 1:
        print('NO')
    else:
        print('YES')


import math

t = int(input())

for q in range(t):
    n = int(input())
    L = [int(i) for i in input().split()]
    G = list(sorted(L))
    f = min(L)
    t = True
    for i in range(n):
        if L[i] % f != 0 and G[i] != L[i]:
            t = False
    if t:
        print('YES')
    else:
        print('NO')


for _ in range(int(input())):
    n = int(input())
    a = list(map(int,input().split()))
    cur = min(a);
    b = sorted(a);
    good = 1
    
    for i in range(n):
        if (a[i] != b[i] and a[i]%cur > 0):
            good = 0;
    
    if good:
        print("YES")
    else:
        print("NO")


import sys
input = sys.stdin.readline
for nt in range(int(input())):
	n = int(input())
	a = list(map(int,input().split()))
	b = sorted(a)
	flag = 0
	for i in range(n):
		if a[i]%b[0]!=0:
			if a[i]!=b[i]:
				flag = 1
				break
	if flag:
		print ("NO")
		continue
	print ("YES")

import sys

T = int(sys.stdin.readline().strip())
for t in range (0, T):
    n = int(sys.stdin.readline().strip())
    a = list(map(int, sys.stdin.readline().strip().split()))
    m = min(a)
    b = sorted(a)
    v = True
    for i in range (0, n):
        if a[i] != b[i] and a[i] % m != 0:
            v = False
    if v == True:
        print("YES")
    else:
        print("NO")

from math import gcd
for _ in range(int(input())):
    N = int(input())
    List = [int(x) for x in input().split()]
    Sorted = List.copy()
    Sorted.sort()
    Min = Sorted[0]
    flag = 0
    for i in range(N):
        if(List[i] != Sorted[i]):
            if(gcd(List[i],Min) == Min):
                continue
            else:
                flag = 1
                break
    if(flag):
        print("NO")
    else:
        print("YES")

for _ in range(int(input())):
    n = int(input())
    ar1 = list(map(int, input().split()))
    ar2 = [e for e in ar1]
    ar2.sort()
    m = ar2[0]
    if any([ar1[i] % m != 0 and ar1[i] != ar2[i] for i in range(n)]):
        print("NO")
    else:
        print("YES")


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = []
    m = min(a)
    for i in range(n):
        if a[i] % m == 0:
            b.append(a[i])
    b.sort()
    cur = 0
    for j in b:
        while a[cur] % m != 0:
            cur += 1
        a[cur] = j
        cur += 1
    for i in range(1, n):
        if a[i - 1] > a[i]:
            print('NO')
            return
    print('YES')

t = int(input())
for _ in range(t):
    solve()

t = int(input())
for i in range(t):
    n = int(input())
    l = list(map(int, input().split()))
    k = sorted(l)
    c = min(l)
    f = 0
    for j in range(n):
        if (l[j] % c != 0):
            if (l[j] != k[j]):
                print('NO')
                f = 1
                break
    if (f == 0):
        print('YES')


t=int(input())
while(t>0):
    t=t-1
    n=int(input())
    a=input().split()
    b=[]
    for i in range(0,n):
        a[i]=int(a[i])
        b.append(a[i])
    b.sort()
    q=0
    mi=b[0]
    for i in range(0,n):
        if(b[i]%mi!=0):
            if(a[i]!=b[i]):
                q=1
                break
    if(q==0):
        print("YES")
    else:
        print("NO")



def main():
    n = int(input())
    a = [int(s) for s in input().split()]
    b = sorted(a)
    am = min(a)
    for i, e in enumerate(a):
        if e % am != 0 and b[i] != e:
            return "NO"
    return "YES"





tests = int(input())
for _ in range(tests):
    print(main())

import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7

for t in range(int(data())):
    n=int(data())
    a=mdata()
    a1=sorted(a)
    k=1
    for i in range(n):
        if a[i]!=a1[i] and a[i]%a1[0]!=0:
            k=0
            break
    if k:
        out("YES")
    else:
        out("NO")

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    mi=min(a)
    b=a[:]
    b.sort()
    if b==a:
        print("YES")
    else:
        for i in range(n):
            if a[i]!=b[i]:
                if a[i]%mi:
                    print("NO")
                    break
        else:
            print("YES")
            


for _ in range(int(input())):
    n = int(input())
    l = list(map(int,input().split()))
    l1 = sorted(l)
    l2 = []
    mi = l1[0]
    ans = 0
    for i in range(n):
        if l[i]%mi != 0:
            if l1[i] != l[i]:
                ans = 1
                break
    if ans == 0:
        print("YES")
    else:
        print("NO")
        


t=int(input())
for i in range(t):
    n=int(input())
    a=list(map(int, input().split()))
    b=sorted(a)
    p=b[0]
    f=False
    for j in range(n):
        if a[j]%p!=0:
            if a[j]!=b[j]:
                f=True
    if f:
        print('NO')
    else:
        print('YES')