Integer to binary

There are several observations we can make about the binary representation of the number:

The last bit represents if the number is divisible by 2 or not. If it’s 1 ⇒ the number is odd, if it’s 0 ⇒ the number is even. This happens because we add powers of 2 which are even numbers all the way except the last bit. The sum of even numbers will always be even, so, the only way to make the number odd is by adding 1 to that even number. And adding 1 is only possible if the last bit of the number is 1.

Dividing the number by 2 is basically “shifting” the binary representation to the right and removing the last bit. In case we do an integer division and discard the remainder, we can think of dividing n by 2 as shifting the binary representation to the right (dividing all the powers of 2 by 2). If n = a + b + c + d, and all a, b, c, and d are powers of 2. Then dividing n by 2, is the same as dividing the sum by 2 ⇒ n/2 = a/2 + b/2 + c/2 + d/2.

Similarly, multiplying a number by 2 is basically “shifting” the binary representation to the left and adding one 0 on the right. We can think of multiplying all the powers of 2 by 2. If n = a + b + c + d, and all a, b, c, and d are powers of 2. Then multiplying n by 2, is the same as multiplying the sum by 2 ⇒ n·2 = a·2 + b·2 + c·2 + d·2.

These observations are very helpful to form an intuition about binary numbers and what they represent. They appear in the most subtle ways in different problems and have a wide usage when working with binary representations.

Having an integer n (like 311), we can get the value of the last bit in the binary representation by checking if the number is divisible by 2:

311 is an odd number ⇒ the last bit is going to be 1 (result = 1). Then we can “shift” the binary representation by dividing 311 by 2 and discarding the last bit which we already know was 1.

311 / 2 = 155 ⇒ 155 is also odd ⇒ the last bit is also 1 (result = 11). We can discard that bit by dividing the number by 2.

155 / 2 = 77 ⇒ 77 is also odd ⇒ the last bit is also 1 (result = 111). Let’s discard the last bit by dividing 77 by 2.

77 / 2 = 38 ⇒ 38 is even ⇒ the last bit is 0 this time (result = 0111).

38 / 2 = 19 ⇒ 19 is even ⇒ the last bit is 1 (result = 10111).

19 / 2 = 9 ⇒ odd (result = 110111).

9 / 2 = 4 ⇒ even (result = 0110111).

4 / 2 = 2 ⇒ even (result = 00110111).

2 / 2 = 1 ⇒ odd (result = 100110111).

1 / 2 = 0 ⇒ we stop here.

So, by “shifting” the binary representation and checking for the number to be odd or even, we got the binary representation.

Power of 2
Power of 2 in decimal	512	256	128	64	32	16	8	4	2	1
Binary (include/exclude)	0	1	0	0	1	1	0	1	1	1
Sum (311)	311	311	55	55	55	23	7	7	3	1

Challenge

Given an integer n, you are asked to find its binary representation.

Input

The only line of the input contains a single integer n (1 ≤ n ≤ ).

Output

The program should print the binary representation. The first bit should always be 1.

Examples

Input	Output
311	100110111
5	101
6	110
7	111

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB