[neerc2011]Gcd guessing game

时间限制:10s      空间限制:128MB

题目描述

         给定一个数n ,有一个数x , ( 1<=x<=n ) 每次你可以猜在[1,n]中的数,假设是y,如果x==y,游戏结束,如果没猜中,则告诉你gcd(x,y),然后继续猜,直到猜中为止。
         现在问给定n的情况下,最坏情况下最少要多少次猜中
 


输入格式

         N
 


输出格式

         最坏情况下最少猜中次数


样例输入

6

样例输出

2

提示

2 ≤ n ≤ 10000.


题目来源

没有写明来源