def f(n):
Q = [1]
dst = [(99, 1)] * n
dst[1] = (1, 1)
for x in Q:
for b in (0, 1):
y = (x * 2 + b) % n
nxt = (dst[x][0] + b, dst[x][1] * 2 + b)
if nxt < dst[y]:
Q.append(y)
dst[y] = nxt
return dst[0][1] // n
while 1:
print(f(int(input())))
Note that non-ascii characters in the above source code will be escaped (such as \x9f).