C. Mere Array

C. Mere Array

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array a1,a2,…,ana1,a2,…,an where all aiai are integers and greater than 00.

In one operation, you can choose two different indices ii and jj (1≤i,j≤n1≤i,j≤n). If gcd(ai,aj)gcd(ai,aj) is equal to the minimum element of the whole array aa, you can swap aiai and ajaj. gcd(x,y)gcd(x,y) denotes the greatest common divisor (GCD) of integers xx and yy.

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

An array aa is non-decreasing if and only if a1≤a2≤…≤ana1≤a2≤…≤an.

Input

The first line contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases.

The first line of each test case contains one integer nn (1≤n≤1051≤n≤105) — the length of array aa.

The second line of each test case contains nn positive integers a1,a2,…ana1,a2,…an (1≤ai≤1091≤ai≤109) — the array itself.

It is guaranteed that the sum of nn over all test cases doesn't exceed 105105.

Output

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

Example

input

Copy

4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4

output

Copy

YES
YES
YES
NO

Note

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

In the second sample, we can swap a1a1 and a3a3 first, and swap a1a1 and a5a5 second to make the array non-decreasing.

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

=========================================================================

非常巧妙的一个题目，首先来说，一个无规则数列进行排序，只需要将排序之后与原位置不对应的位置进行对比即可，也就是排序之后与排序之后位置上数字不对应的需要进行排序。

而我们根据冒泡排序等各种排序规则，两元素若能够自由交换，那么一定能够排序成功，而本题要求的条件略有苛刻，那就是要直接交换两个元素的话，必须满足gcd=mina，这个条件太苛刻了，我们冒泡排序无法成功。但是我们可以将这个条件再降一下标准

a b能够整除min，那么一定能够交换

证明如下

x  min   y  其中gcd(x,y)=k min 也就是x,y目前无法进行交换

min x y

y x min 

y min x

三步走，完成交换，min位置不变

#include<iostream>
#include<cstdio>
#include<queue>
# include<algorithm>
using namespace std;
int b[100000+10];
int a[100000+10];

int main()
{

    int t;
    cin>>t;

    while(t--)
    {
        int n,flag=0;
        cin>>n;

        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            b[i]=a[i];
        }
        sort(b+1,b+1+n);

        for(int i=1;i<=n;i++)
        {
            if(a[i]!=b[i])
            {
                if(b[i]%b[1])
                {
                    flag=1;
                    break;
                }
            }
        }

        if(flag)
        {
            cout<<"No"<<endl;
        }
        else
        {
            cout<<"YES"<<endl;

        }
    }

    return 0;
}