시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 32 14 14 50.000%

문제

상근이와 정인이는 숫자 맞추기 게임을 하고 있다.

먼저, 정인이는 1보다 크거나 같고, n보다 작거나 같은 자연수 하나를 생각한다.

상근이는 정인이에게 생각한 숫자가 x인지 물어볼 수 있다. 이때 정인이는 자신이 생각한 숫자와 x의 최대공약수가 몇 인지 말해준다.

다음은 n=6일 때 가능한 상근이와 정인이의 대화이다.

상근: 3이야?

정인: 3이랑 내가 생각한 숫자의 최대공약수는 1이야.

상근: (음... 그럼 3이랑 6은 아니네? 근데 1,2,4,5는 될 수 있어!) 그럼 2야?

정인: 2랑 내가 생각한 숫자의 최대공약수는 2야.

상근: (오!? 그럼 1, 5는 아니겠네?) 너가 생각한 숫자는 4야 맞지?

정인: 4랑 내가 생각한 숫자의 최대공약수는 2야.

상근: 그럼 니가 생각한 숫자는 2네 ㅋㅋㅋ

위의 예에서 상근이는 정인이가 생각한 숫자를 맞추기 위해서 질문을 총 3번 했다. 하지만, n=6인 경우에 항상 2번의 질문으로 정인이가 생각한 숫자를 맞출 수 있다.

제일 먼저 상근이는 6을 물어보면 된다. 만약 정인이가 1이라고 대답했다면, 정인이가 생각한 숫자는 1과 5중 하나이기 때문에, 2번 질문으로 맞출 수 있다. 정인이의 대답이 2라면, 정인이가 생각한 숫자는 2와 4중 하나이다. 만약, 정인이가 3이라고 대답했다면, 정답은 3이고, 6이라고 대답했다면 6이다.

따라서, 상근이는 최대 2번의 질문으로 정인이가 생각한 숫자를 맞출 수 있다.

n이 주어졌을 때, 상근이가 최적의 방법으로 질문했을 때, 최대 몇 번 만에 정인이가 생각한 숫자를 맞출 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. 2 ≤ n ≤ 10,000

출력

첫째 줄에 상근이가 최적의 방법으로 질문했을 때, 최대 몇 번의 질문으로 정인이가 생각한 숫자를 맞출 수 있는지 출력한다.

예제 입력 1

6

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjM1MDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMTggXHViOWRlXHVjZDk0XHVhZTMwIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgXHVjMjJiXHVjNzkwIFx1YjlkZVx1Y2Q5NFx1YWUzMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViYTNjXHVjODAwLCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBuXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MTVcdWM3NzhcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YWMwMCB4XHVjNzc4XHVjOWMwIFx1YmIzY1x1YzViNFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNjQwIHhcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHVhYzAwIFx1YmE4NyBcdWM3NzhcdWM5YzAgXHViOWQwXHVkNTc0XHVjOTAwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGNcdWM3NDAgbj02XHVjNzdjIFx1YjU0YyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yzc1OCBcdWIzMDBcdWQ2NTRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmYzogM1x1Yzc3NFx1YzU3Yz88XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjODE1XHVjNzc4OiAzXHVjNzc0XHViNzkxIFx1YjBiNFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1YjI5NCAxXHVjNzc0XHVjNTdjLjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmM6IChcdWM3NGMuLi4gXHVhZGY4XHViN2ZjIDNcdWM3NzRcdWI3OTEgNlx1Yzc0MCBcdWM1NDRcdWIyYzhcdWIxMjQ/IFx1YWRmY1x1YjM3MCAxLDIsNCw1XHViMjk0IFx1YjQyMCBcdWMyMTggXHVjNzg4XHVjNWI0ISkgXHVhZGY4XHViN2ZjIDJcdWM1N2M/PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgxNVx1Yzc3ODogMlx1Yjc5MSBcdWIwYjRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMThcdWIyOTQgMlx1YzU3Yy48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjOiAoXHVjNjI0IT8gXHVhZGY4XHViN2ZjIDEsIDVcdWIyOTQgXHVjNTQ0XHViMmM4XHVhY2EwXHViMTI0PykgXHViMTA4XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWIyOTQgNFx1YzU3YyBcdWI5ZGVcdWM5YzA/PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgxNVx1Yzc3ODogNFx1Yjc5MSBcdWIwYjRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMThcdWIyOTQgMlx1YzU3Yy48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjOiBcdWFkZjhcdWI3ZmMgXHViMmM4XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWIyOTQgMlx1YjEyNCBcdTMxNGJcdTMxNGJcdTMxNGI8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzA0XHVjNzU4IFx1YzYwOFx1YzVkMFx1YzExYyBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWI5N2MgXHViOWRlXHVjZDk0XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM5YzhcdWJiMzhcdWM3NDQgXHVjZDFkIDNcdWJjODggXHVkNTg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIG49Nlx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDAgXHVkNTZkXHVjMGMxIDJcdWJjODhcdWM3NTggXHVjOWM4XHViYjM4XHVjNzNjXHViODVjIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YjlkZVx1Y2Q5YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM4MWNcdWM3N2MgXHViYTNjXHVjODAwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCA2XHVjNzQ0IFx1YmIzY1x1YzViNFx1YmNmNFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgMVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWIzMDBcdWIyZjVcdWQ1ODhcdWIyZTRcdWJhNzQsIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHViMjk0IDFcdWFjZmMgNVx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCAyXHViYzg4IFx1YzljOFx1YmIzOFx1YzczY1x1Yjg1YyBcdWI5ZGVcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjODE1XHVjNzc4XHVjNzc0XHVjNzU4IFx1YjMwMFx1YjJmNVx1Yzc3NCAyXHViNzdjXHViYTc0LCBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YjI5NCAyXHVjNjQwIDRcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCAzXHVjNzc0XHViNzdjXHVhY2UwIFx1YjMwMFx1YjJmNVx1ZDU4OFx1YjJlNFx1YmE3NCwgXHVjODE1XHViMmY1XHVjNzQwIDNcdWM3NzRcdWFjZTAsIDZcdWM3NzRcdWI3N2NcdWFjZTAgXHViMzAwXHViMmY1XHVkNTg4XHViMmU0XHViYTc0IDZcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAyXHViYzg4XHVjNzU4IFx1YzljOFx1YmIzOFx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWI5ZGVcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0blx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWM5YzhcdWJiMzhcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmM4OCBcdWI5Y2NcdWM1ZDAgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWI5N2MgXHViOWRlXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAyICZsZTsgbiAmbGU7IDEwLDAwMDxcL3A+XHJcblxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWNkNWNcdWM4MDFcdWM3NTggXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzljOFx1YmIzOFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHViYzg4XHVjNzU4IFx1YzljOFx1YmIzOFx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWI5ZGVcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM1MDEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHQ0QgR3Vlc3NpbmcgR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+UGF1bCBoYWQgYSBiaXJ0aGRheSB5ZXN0ZXJkYXksIGFuZCB0aGV5IHdlcmUgcGxheWluZyBhIGd1ZXNzaW5nIGdhbWUgdGhlcmUgd2l0aCBBbmRyZXc6IEFuZHJldyB3YXMgdHJ5aW5nIHRvIGd1ZXNzIFBhdWwmcnNxdW87cyBhZ2UuIEFuZHJldyBrbmV3IHRoYXQgUGF1bCZyc3F1bztzIGFnZSBpcyBhbiBpbnRlZ2VyIGJldHdlZW4gMSBhbmQgbiwgaW5jbHVzaXZlLiBBbmRyZXcgY2FuIGd1ZXNzIGFueSBudW1iZXIgeCBiZXR3ZWVuIDEgYW5kIG4sIGFuZCBQYXVsIHdpbGwgdGVsbCBoaW0gd2hhdCBpcyB0aGUgZ3JlYXRlc3QgY29tbW9uIGRpdmlzb3Igb2YgeCBhbmQgaGlzIGFnZS48XC9wPlxyXG5cclxuPHA+SGVyZSZyc3F1bztzIGEgcG9zc2libGUgY291cnNlIG9mIHRoZSBnYW1lIGZvciBuID0gNi4gQW5kcmV3IHN0YXJ0cyB3aXRoIGd1ZXNzaW5nIDMsIGFuZCBQYXVsIHJlcGxpZXMgdGhhdCB0aGUgZ3JlYXRlc3QgY29tbW9uIGRpdmlzb3Igb2YgMyBhbmQgaGlzIGFnZSBpcyAxLiBUaGF0IG1lYW5zIHRoYXQgUGF1bCZyc3F1bztzIGFnZSBjYW4mcnNxdW87dCBiZSAzIG9yIDYsIGJ1dCBjYW4gc3RpbGwgYmUgMSwgMiwgNCBvciA1LiBBbmRyZXcgY29udGludWVzIHdpdGggZ3Vlc3NpbmcgMiwgYW5kIFBhdWwgcmVwbGllcyAyLiBUaGF0IG1lYW5zIHRoYXQgUGF1bCZyc3F1bztzIGFnZSBjYW4mcnNxdW87dCBiZSAxIG9yIDUsIGFuZCB0aGUgb25seSB0d28gcmVtYWluaW5nIGNob2ljZXMgYXJlIDIgYW5kIDQuIEZpbmFsbHksIEFuZHJldyBndWVzc2VzIDQsIGFuZCBQYXVsIHJlcGxpZXMgMi4gVGhhdCBtZWFucyB0aGF0IFBhdWwmcnNxdW87cyBhZ2UgaXMgMiwgYW5kIHRoZSBnYW1lIGlzIG92ZXIuPFwvcD5cclxuXHJcbjxwPkFuZHJldyBuZWVkZWQgdGhyZWUgZ3Vlc3NlcyBpbiB0aGUgYWJvdmUgZXhhbXBsZSwgYnV0IGl0JnJzcXVvO3MgcG9zc2libGUgdG8gYWx3YXlzIGRldGVybWluZSBQYXVsJnJzcXVvO3MgYWdlIGluIGF0IG1vc3QgdHdvIGd1ZXNzZXMgZm9yIG4gPSA2LiBUaGUgb3B0aW1hbCBzdHJhdGVneSBmb3IgQW5kcmV3IGlzOiBhdCB0aGUgXHVmYjAxcnN0IHN0ZXAsIGd1ZXNzIDYuIElmIFBhdWwgc2F5cyAxLCB0aGVuIGl0cyAxIG9yIDUgYW5kIGhlIGNhbiBjaGVjayB3aGljaCBvbmUgYnkgZ3Vlc3NpbmcgNS4gSWYgUGF1bCBzYXlzIDIsIHRoZW4gaXRzIDIgb3IgNCwgYW5kIGhlIGNhbiBjaGVjayBieSBndWVzaW5nIDQgYXMgd2UmcnNxdW87dmUgc2VlbiBhYm92ZS4gSWYgUGF1bCBzYXlzIDMsIHRoZW4gd2UgYWxyZWFkeSBrbm93IHRoZSBhbnN3ZXIgaXMgMy4gRmluYWxseSwgaWYgUGF1bCBzYXlzIDYsIHRoZSBhbnN3ZXIgaXMgNi48XC9wPlxyXG5cclxuPHA+V2hhdCBpcyB0aGUgbnVtYmVyIG9mIGd1ZXNzZXMgcmVxdWlyZWQgaW4gdGhlIHdvcnN0IGNhc2UgaWYgQW5kcmV3IGd1ZXNzZXMgb3B0aW1hbGx5IGZvciB0aGUgZ2l2ZW4gbj88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBcdWZiMDFsZSBjb250YWlucyBvbmUgaW50ZWdlciBuLCAyICZsZTsgbiAmbGU7IDEwIDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGludGVnZXIgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGd1ZXNzZXMgQW5kcmV3IHdpbGwgbmVlZCB0byBtYWtlIGluIHRoZSB3b3JzdCBjYXNlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==