문제
주황이와 성현이가 "거듭제곱 써리원" 게임을 한다. "거듭제곱 써리원" 게임은 두 사람이 번갈아가면서 1부터 순서대로 한 개 이상의 연속한 수들을 부르는 게임이다. 이 때, 부르는 개수에는 크기 제한은 없지만 무조건 2의 거듭제곱(1 포함)이여야 한다.
한편, 게임 시작 전 주황이와 성현이는 임의로 세계수(世界數)를 정해 둔 후 게임을 시작하는데, 세계수를 말하는 쪽이 진다.
성현이가 주황이에 비해 훨씬 머리가 좋기 때문에 주황이가 매번 게임에서 진다.
성현이를 이겨보고 싶어 하는 주황이는 게임 시작 시 몇 개의 수를 말해야 하는 지 알려달라고 한다. 처음에 주황이가 몇 개의 수를 말해야 하는지 구하여라.
[서브태스크]
서브태스크 1 : 세계수의 값은 30 이하이고 테스트 케이스의 수가 10 이하이다.
서브태스크 2 : 세계수의 값은 10,000 이하이고 테스트 케이스의 수가 500 이하이다.
서브태스크 3 : 세계수의 값은 1,000,000 이하이다.
서브태스크 4 : 세계수의 값은 109 이하이다.
서브태스크 5 : 추가적인 제약조건은 없다.
입력
입력은 테스트 케이스 형식으로 주어진다. 각 테스트 케이스마다, 세계수의 값을 나타내는 1 이상 1015 이하의 자연수가 주어진다.
입력은 0이 주어질 때까지 들어온다. 단, 테스트 케이스의 수는 20,000 이하이다.
출력
각 테스트 케이스마다 한 줄에 하나씩 답을 출력한다.
만약 주황이가 이길 수 없다면 -1을 출력하고, 그렇지 않으면 주황이가 이기기 위해 처음에 말해야 하는 수의 개수 중 가장 큰 것을 출력한다.
예제
3
7
11
0
2
-1
4
로그인해야 코드를 작성할 수 있어요.