PhiFunction

#include<bits/stdc++.h>
using namespace std;


#define pb push_back
#define ll long long
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define M 100007
#define INF 1e9
#define INFL 1e18
#define PI acos(-1)
#define mp make_pair
#define fast_in_out ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Max 1000000
int phi[Max];




int PhiFunc(ll n)
{
    ll result=n;
    for(ll i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            while(n%i==0)
            {
                n/=i;
            }
            result-=result/i;
        }
    }
    if(n>1)
    {
        result-=result/n;
    }
    return result;
}
void phi_1_to_n(int n)//nloglogn
{
    vector<int>phi(n+1);
    phi[0]=0;
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        phi[i]=i;
    }
    for(int i=2;i<=n;i++)
    {
        if(phi[i]==i)
        {
            for(int j=i;j<=n;j+=i)
            {
                phi[j]-=phi[j]/i;
            }
        }
    }
}

void phi_1_to_n(int n)//nlogn
{
    vector<int>phi(n+1);
    phi[0]=0;
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        phi[i]=i-1;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=2*i;j<=n;j+=i)
        {
            phi[j]-=phi[i];
        }
    }
}