watnum2

#include<stdio.h>
#include<math.h>
#define     MAX    2000002
unsigned long int ziValues[MAX];
unsigned long int getGcd(unsigned long int greater, unsigned long int lesser)
{
    unsigned long int modval = (greater%lesser);
    if(modval==0)
    return lesser;
    return getGcd(lesser,greater%lesser);
}
unsigned long int gcd(unsigned long int a, unsigned long int b)
{
         if(a>b)
         return getGcd(a,b);
         else
         return getGcd(b,a);
}
long int getNoQns(unsigned long int num)
{
    long int pos = 0;
    while(num>1)
    {
        num=((num+1)/2u);
        pos++;
    }
    return pos;
}
unsigned long int getZiVal(unsigned long int num)
{
    unsigned long int n, fcnt, primeflag = 1, limit, factor;
    double tmp;
    tmp = (double)num;
    limit = (int)sqrt(tmp)+1;
/*    printf("%lu - %lu",num, limit);*/
    for(n=2u;n<=limit && n<num;n++)
    {
        if(num%n==0)
        {
            if(primeflag==1)
            {
                factor=n;
                primeflag = 0;
            }
            if(gcd(n, num/n)==1)
            {
                ziValues[num]=ziValues[n]*ziValues[num/n];
                return ziValues[num];
            }
        }
    }
    if(primeflag == 1)
    {
        ziValues[num] = (num-1);
        return ziValues[num];
    }
/*    printf("%");
    fcnt=0l;
    for(n=1;n<num;n++)
    {
        if(gcd(num, n)==1)
        {
            fcnt++;
        }
    }
    ziValues[num]=fcnt;*/
    ziValues[num]=(num-num/factor);
    return ziValues[num];
}
int main()
{
    unsigned long int iter, cnt, n;
    scanf("%lu",&n);
    cnt=0u;
    for(iter=2u;iter<=n;iter++)
    {
          cnt+=getZiVal(iter);
/*          printf("+%lu\n",cnt);*/
    }
    printf("%ld\n",getNoQns(cnt));
    return 0;
}