bool prime(int q)

 {

     if(q==||q==) return ;

     if(q==) return ;

     if(q%!=||q%!=) return ;

     int cnt=sqrt(q);

     for(int i=;i<=cnt;i+=)

         if(q%!=||q%(i+)!=) return ;

     return ;

 }

 //埃氏筛 筛出1~n的素数

 void prime_select()

 {

     for(int i=;i<=n;i++)

     {

         if(vis[i]) continue;

         printf("%d\n",i);

         for(int j=n;j<=n/i;j++) vis[i*j]=;

     }

 } 

 //线性筛

 void prime_select()

 {

     //v[]记录下标数的最小质因子 初值为0

     for(int i=;i<=n;i++)

     {

         if(v[i]==) v[i]=i,prime[++m]=i;

         for(int j=;j<=m;j++)

         {//i是比prime[j]更小的质因子or超出n的范围

             if(prime[j]>v[i]||prime[j]>n/i) break;

             v[i*prime[j]]=prime[j];

         }

     }

 }

 //质因数分解--基于算术基本定理 复杂度O（根号n）

 void divide()

 {

     for(int i=;i<=sqrt(n);i++)

         if(n%i==)

         {

             p[++m]=i;c[m]=;

             while(n%i==) n/=i,c[m]++;

         }

     if(n>) p[++m]=n,c[m]=;

     for(int i=;i<=m;i++)

         printf("%d^%d\n",p[i],c[i]);

 } 

//求1~N每个数的正约数集合--倍数法

void work()

{

    vector<int>fac[];

    for(int i=;i<=n;i++)

        for(int j=;j<=n/i;j++)

            fac[i*j].push_back(i);

}

int gcd(int a,int b)

{

    return b ? gcd(b,a%b) : a;

}//辗转相除

int gcd(int a,int b)

{

    while(a!=b)

    {

        if(a>b)

            a-=b;

        else

            b-=a;

    }

    return a;

}//更相减损

void phi()

{

    phi[]=;

    for(int i=;i<=n;i++) phi[i]=i;

    for(int i=;i<=n;i++)

        if(phi[i]==i)

            for(int j=i;j<=n;j+=i)

                phi[j]=phi[j]/i*(i-);

}