A positive integer N is a base-b palindrome if the base-b representation of N is a palindrome, i.e. reads the same way in either direction. For instance, 7 (base 10) is a palindrome in any base greater than or equal to 8. It is also a palindrome in base 2 (111) and 6 (11), but not in 3 (21), 4 (13), 5 (12), or 7 (10). The first four base 2 palindromes (written in base 10) are 1, 3, 5, and 7.</p>

You are supposed to find the M-th base-2 palindrome and output its base 10 representation.

입력 형식

The input is a single line with a single positive integer M ≤ 50 000 in base 10.

출력 형식

The output for input M should be a single line with the base 10 representation of the M-th base-2 palindrome.

예제 입력 1

1

예제 출력 1

1

예제 입력 2

3

예제 출력 2

5