当前没有测试数据。

Description

一个二进制数（无前导0），如果其中 0 和 1 的个数相同，则称它为“平衡数”。

不难得出，比较小的前几个“平衡数”依次为：

10

1001

1010

1100

100011

100101

……

现在输入一个正整数 k，请你输出第 k 小的“平衡数”。

Input

一个整数 k

Output

一个二进制整数（无前导0），表示第 k 小的“平衡数”。

Samples

2

1001

123456789

Data Size

100% 的数据：1 ≤ K ≤ 2^60。