[sgu348] Twisting the Number

题目描述

Dull 教授发明了一种新的数论概念——“扭转生成器”。

对于一个正整数 $p$，设它的二进制表示共有 $b$ 位，最高位为 $1$。对这 $b$ 位二进制表示做所有可能的循环移位，共有 $b$ 种结果。把这些结果对应的整数构成集合 $W(p)$。注意，循环移位后的二进制串允许以 $0$ 开头。

例如，$11$ 的二进制表示为 1011，其所有循环移位对应的整数构成

$W(11)=\{7,11,13,14\}$。

如果

$\displaystyle \bigcup_{k=1}^{p} W(k)$

包含集合 $\{1,2,\ldots,n\}$，则称 $p$ 是整数 $n$ 的一个扭转生成器。

给定正整数 $n$，求它的最小扭转生成器。

输入格式

输入一行，一个正整数 $n$。

$1\le n\le10^{18}$。

输出格式

输出一个整数，表示 $n$ 的最小扭转生成器。

样例

6

5

数据范围

$1\le n\le10^{18}$。