题目描述

有 $n$ 个盒子，开始时每个盒子中有一个棋子。

两位选手轮流操作，每次可以选择一个 $i$ 号盒子中的棋子和一个正整数 $p$，将棋子移到编号为 $2^p\times i$ 的盒子中。若编号为 $2^p\times i$ 的盒子中已有棋子了，则这两个棋子都会被移出盒子。不能移动者输。

求第 $k$ 小的 $n$，使得后手能赢得游戏。

输入格式

仅一行，包含一个正整数 $k$。

输出格式

仅一行，包含一个正整数 $n$。

2

10

提示

对于 $100\%$ 的数据，$1\le k<10^9$。