Description

一个数A，如果它转成二进制后B。A是B的后缀，这个数就是我们所要的。

现在给出数字N，求第N个这样的数（1 ≤ n ≤ 10000）

Format

Input

Output

Samples

2

10

Limitation