시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHJcblx0XHViYTNjXHVjODAwLCBcdWM4MTVcdWM3NzhcdWM3NzRcdWIyOTQgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCBuXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4MTVcdWM3NzhcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YWMwMCB4XHVjNzc4XHVjOWMwIFx1YmIzY1x1YzViNFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViNTRjIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YzY0MCB4XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1YWMwMCBcdWJhODcgXHVjNzc4XHVjOWMwIFx1YjlkMFx1ZDU3NFx1YzkwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjXHVjNzQwIG49Nlx1Yzc3YyBcdWI1NGMgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzY0MCBcdWM4MTVcdWM3NzhcdWM3NzRcdWM3NTggXHViMzAwXHVkNjU0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmM6IDNcdWM3NzRcdWM1N2M/PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgxNVx1Yzc3ODogM1x1Yzc3NFx1Yjc5MSBcdWIwYjRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMThcdWIyOTQgMVx1Yzc3NFx1YzU3Yy48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjOiAoXHVjNzRjLi4uIFx1YWRmOFx1YjdmYyAzXHVjNzc0XHViNzkxIDZcdWM3NDAgXHVjNTQ0XHViMmM4XHViMTI0PyBcdWFkZmNcdWIzNzAgMSwyLDQsNVx1YjI5NCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YzViNCEpIFx1YWRmOFx1YjdmYyAyXHVjNTdjPzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM4MTVcdWM3Nzg6IDJcdWI3OTEgXHViMGI0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHViMjk0IDJcdWM1N2MuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmYzogKFx1YzYyNCE/IFx1YWRmOFx1YjdmYyAxLCA1XHViMjk0IFx1YzU0NFx1YjJjOFx1YWNhMFx1YjEyND8pIFx1YjEwOFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHViMjk0IDRcdWM1N2MgXHViOWRlXHVjOWMwPzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM4MTVcdWM3Nzg6IDRcdWI3OTEgXHViMGI0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHViMjk0IDJcdWM1N2MuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzBjMVx1YWRmYzogXHVhZGY4XHViN2ZjIFx1YjJjOFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHViMjk0IDJcdWIxMjQgXHUzMTRiXHUzMTRiXHUzMTRiPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM1ZDBcdWMxMWMgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YjlkZVx1Y2Q5NFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjOWM4XHViYjM4XHVjNzQ0IFx1Y2QxZCAzXHViYzg4IFx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBuPTZcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1ZDU2ZFx1YzBjMSAyXHViYzg4XHVjNzU4IFx1YzljOFx1YmIzOFx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWI5ZGVcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjODFjXHVjNzdjIFx1YmEzY1x1YzgwMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgNlx1Yzc0NCBcdWJiM2NcdWM1YjRcdWJjZjRcdWJhNzQgXHViNDFjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIDFcdWM3NzRcdWI3N2NcdWFjZTAgXHViMzAwXHViMmY1XHVkNTg4XHViMmU0XHViYTc0LCBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YjI5NCAxXHVhY2ZjIDVcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgMlx1YmM4OCBcdWM5YzhcdWJiMzhcdWM3M2NcdWI4NWMgXHViOWRlXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yzc1OCBcdWIzMDBcdWIyZjVcdWM3NzQgMlx1Yjc3Y1x1YmE3NCwgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWIyOTQgMlx1YzY0MCA0XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgM1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWIzMDBcdWIyZjVcdWQ1ODhcdWIyZTRcdWJhNzQsIFx1YzgxNVx1YjJmNVx1Yzc0MCAzXHVjNzc0XHVhY2UwLCA2XHVjNzc0XHViNzdjXHVhY2UwIFx1YjMwMFx1YjJmNVx1ZDU4OFx1YjJlNFx1YmE3NCA2XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMlx1YmM4OFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWI5N2MgXHViOWRlXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjOWM4XHViYjM4XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWJjODggXHViOWNjXHVjNWQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YjlkZVx1Y2Q5YyBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMiAmbGU7IG4gJmxlOyAxMCwwMDA8XC9wPlxyXG5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWM5YzhcdWJiMzhcdWQ1ODhcdWM3NDQgXHViNTRjLCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmM4OFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWI5N2MgXHViOWRlXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNTAxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR0NEIEd1ZXNzaW5nIEdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPlBhdWwgaGFkIGEgYmlydGhkYXkgeWVzdGVyZGF5LCBhbmQgdGhleSB3ZXJlIHBsYXlpbmcgYSBndWVzc2luZyBnYW1lIHRoZXJlIHdpdGggQW5kcmV3OiBBbmRyZXcgd2FzIHRyeWluZyB0byBndWVzcyBQYXVsJnJzcXVvO3MgYWdlLiBBbmRyZXcga25ldyB0aGF0IFBhdWwmcnNxdW87cyBhZ2UgaXMgYW4gaW50ZWdlciBiZXR3ZWVuIDEgYW5kIG4sIGluY2x1c2l2ZS4gQW5kcmV3IGNhbiBndWVzcyBhbnkgbnVtYmVyIHggYmV0d2VlbiAxIGFuZCBuLCBhbmQgUGF1bCB3aWxsIHRlbGwgaGltIHdoYXQgaXMgdGhlIGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yIG9mIHggYW5kIGhpcyBhZ2UuPFwvcD5cclxuXHJcbjxwPkhlcmUmcnNxdW87cyBhIHBvc3NpYmxlIGNvdXJzZSBvZiB0aGUgZ2FtZSBmb3IgbiA9IDYuIEFuZHJldyBzdGFydHMgd2l0aCBndWVzc2luZyAzLCBhbmQgUGF1bCByZXBsaWVzIHRoYXQgdGhlIGdyZWF0ZXN0IGNvbW1vbiBkaXZpc29yIG9mIDMgYW5kIGhpcyBhZ2UgaXMgMS4gVGhhdCBtZWFucyB0aGF0IFBhdWwmcnNxdW87cyBhZ2UgY2FuJnJzcXVvO3QgYmUgMyBvciA2LCBidXQgY2FuIHN0aWxsIGJlIDEsIDIsIDQgb3IgNS4gQW5kcmV3IGNvbnRpbnVlcyB3aXRoIGd1ZXNzaW5nIDIsIGFuZCBQYXVsIHJlcGxpZXMgMi4gVGhhdCBtZWFucyB0aGF0IFBhdWwmcnNxdW87cyBhZ2UgY2FuJnJzcXVvO3QgYmUgMSBvciA1LCBhbmQgdGhlIG9ubHkgdHdvIHJlbWFpbmluZyBjaG9pY2VzIGFyZSAyIGFuZCA0LiBGaW5hbGx5LCBBbmRyZXcgZ3Vlc3NlcyA0LCBhbmQgUGF1bCByZXBsaWVzIDIuIFRoYXQgbWVhbnMgdGhhdCBQYXVsJnJzcXVvO3MgYWdlIGlzIDIsIGFuZCB0aGUgZ2FtZSBpcyBvdmVyLjxcL3A+XHJcblxyXG48cD5BbmRyZXcgbmVlZGVkIHRocmVlIGd1ZXNzZXMgaW4gdGhlIGFib3ZlIGV4YW1wbGUsIGJ1dCBpdCZyc3F1bztzIHBvc3NpYmxlIHRvIGFsd2F5cyBkZXRlcm1pbmUgUGF1bCZyc3F1bztzIGFnZSBpbiBhdCBtb3N0IHR3byBndWVzc2VzIGZvciBuID0gNi4gVGhlIG9wdGltYWwgc3RyYXRlZ3kgZm9yIEFuZHJldyBpczogYXQgdGhlIFx1ZmIwMXJzdCBzdGVwLCBndWVzcyA2LiBJZiBQYXVsIHNheXMgMSwgdGhlbiBpdHMgMSBvciA1IGFuZCBoZSBjYW4gY2hlY2sgd2hpY2ggb25lIGJ5IGd1ZXNzaW5nIDUuIElmIFBhdWwgc2F5cyAyLCB0aGVuIGl0cyAyIG9yIDQsIGFuZCBoZSBjYW4gY2hlY2sgYnkgZ3Vlc2luZyA0IGFzIHdlJnJzcXVvO3ZlIHNlZW4gYWJvdmUuIElmIFBhdWwgc2F5cyAzLCB0aGVuIHdlIGFscmVhZHkga25vdyB0aGUgYW5zd2VyIGlzIDMuIEZpbmFsbHksIGlmIFBhdWwgc2F5cyA2LCB0aGUgYW5zd2VyIGlzIDYuPFwvcD5cclxuXHJcbjxwPldoYXQgaXMgdGhlIG51bWJlciBvZiBndWVzc2VzIHJlcXVpcmVkIGluIHRoZSB3b3JzdCBjYXNlIGlmIEFuZHJldyBndWVzc2VzIG9wdGltYWxseSBmb3IgdGhlIGdpdmVuIG4/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgXHVmYjAxbGUgY29udGFpbnMgb25lIGludGVnZXIgbiwgMiAmbGU7IG4gJmxlOyAxMCAwMDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBpbnRlZ2VyICZtZGFzaDsgdGhlIG51bWJlciBvZiBndWVzc2VzIEFuZHJldyB3aWxsIG5lZWQgdG8gbWFrZSBpbiB0aGUgd29yc3QgY2FzZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=