1401_C. Mere Array
You are given an array a_1, a_2, ..., 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 ≤ i, j ≤ 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)](https://en.wikipedia.org/wiki/Greatest_common_divisor) 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 ≤ a_2 ≤ … ≤ a_n.

Input

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

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

The second line of each test case contains n positive integers a_1, a_2, … a_n (1 ≤ a_i ≤ 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.
```python
for i in range(int(input())):
    n=int(input())
    a = [int(x ) for x in input().split()]
    b= a[::-1]

    b.sort()
    z=min(a)
    p=True
    for j in range(n):
        if a[j]!=b[j] :
            if a[j]%z>0:
                p=False
                break
    if p :
        print("YES")
    else:print("NO")
```