#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=3000050;
int phi[maxn],prime[maxn],tot;
bool notprime[maxn];
void isprime(int x){
if(x<2)return 0;
for(int i=int(sqrt(x+0.5));i>=2;i--){
if(x%i==0)return 0;
}
return 1;
}//判断素数
int prime[maxn],tot;
bool nowprime[maxn]={1,1};
void xxs(int n){
for(int i=2;i<=n;i++){
if(!nowprime[i])prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<=n;j++){
notprime[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}//线性筛
int euler(int n){
int m=int(sqrt(n+0.5));
int ans=n;
for(int i=2;i<=m;i++){
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
}
}//求n的欧拉函数值
int n,phi[maxn],prime[maxn],tot;
bool notprime[maxn];
void getphi(){
int i,j,k;
phi[1]=1;
for(i=2;i<=n;i++){
if(!notprime[i])prime[++tot]=i,phi[i]=i-1;
for(j=1;j<=tot;j++){
k=i*prime[j];
if(k>n)break;
notprime[k]=1;
if(i%prime[j]==0){
phi[k]=prime[j]*phi[i];break;
}else{
phi[k]=(prime[j]-1)*phi[i];
}
}
}
}//求1-n的所有欧拉函数值
int main(){
}