종석이와 우주가 "거듭제곱 써리원" 게임을 한다. "거듭제곱 써리원" 게임은 두 사람이 번갈아가면서 1부터 순서대로 한 개 이상의 연속한 수들을 부르는 게임이다. 이 때, 부르는 개수에는 크기 제한은 없지만 무조건 2의 거듭제곱(1 포함)이여야 한다. 한편, 게임 시작 전 종석이와 우주는 임의로 세계수(世界數)를 정해 둔 후 게임을 시작하는데, 세계수를 말하는 쪽이 진다.

우주가 종석이에 비해 훨씬 머리가 좋기 때문에 종석이가 매번 게임에서 진다. 우주를 이겨보고 싶어 하는 종석이는 게임 시작 시 몇 개의 수를 말해야 하는 지 알려달라고 한다. 처음에 종석이가 몇 개의 수를 말해야 하는지 구하여라.

입력

각 테스트 케이스마다, 세계수의 값을 나타내는 1 이상 10^15 이하의 자연수가 주어진다. 입력은 0이 주어질 때까지 들어온다.

출력

만약 종석이가 이길 수 없다면 -1을 출력하고, 그렇지 않으면 종석이가 이기기 위해 처음에 말해야 하는 수의 개수 중 가장 큰 것을 출력한다.

입출력 예

입력

3
7
11
0

출력 

2
-1
4

출처:functionx