Director Shom 2

Interview

Time limit0.5sMemory limit1024 MB

Summary

Given N, find the Nth smallest positive integer that contains at least three consecutive 6s.

Level: Easy3 of 10
Topics: Brute force, Implementation
Solved: No attempts yet

Problem

The number 666 is said to represent the apocalypse, so many blockbuster films use titles that contain 666. Film director Shom makes a series of films called End of the World. When George Lucas made Star Wars, he named the films Star Wars 1, Star Wars 2, up to Star Wars 6, and when Peter Jackson made The Lord of the Rings, he named them The Lord of the Rings 1, The Lord of the Rings 2, and The Lord of the Rings 3. Shom wants to show that he surpasses both Lucas and Jackson, so he decides to name his film titles a little differently. An apocalyptic number is a number that contains at least three consecutive 6s. The smallest apocalyptic number is 666, and the next larger ones are 1666, 2666, 3666, and so on. So Shom names the first film End of the World 666 and the second film End of the World 1666. In general, the title of the Nth film is End of the World followed by the Nth smallest apocalyptic number.

Input

The first line contains N. N is a natural number less than or equal to 13,559,699.

Output

Print the number included in the title of the Nth film on the first line.

Examples5

Example 1
Input
```
2
```
Expected output
```
1666
```
Example 2
Input
```
3
```
Expected output
```
2666
```
Example 3
Input
```
6
```
Expected output
```
5666
```
Example 4
Input
```
187
```
Expected output
```
66666
```
Example 5
Input
```
500
```
Expected output
```
166699
```