You are given a positive integer n. Output its binary notation.

Input

The only line of input data contains an integer n (1 ≤ n ≤ 106).

Output

Output the binary notation of n (without any leading zeros).

Examples

Input

5


Output

101


Input

126


Output

1111110

Note

In the first example 5 = 1 * 22 + 0 * 21 + 1 * 20.

Source: codeforces | Difficulty: MEDIUM_HARD


Solutions: