Movie Director Shom

The number 666 is said to symbolize the end of the world, so many blockbuster movies use 666 in their titles.

Movie director Shom is making a film series called End of the World. Instead of numbering the titles with 1, 2, 3, and so on like other directors, Shom decides to use his own rule.

A doom number is a positive integer whose decimal representation contains at least three consecutive 6s. The smallest doom number is 666, followed by 1666, 2666, 3666, ... .

Shom uses 666 in the title of the first movie and 1666 in the title of the second movie. In general, the N-th movie title contains the N-th smallest doom number.

Given N, write a program that prints the number used in the title of Shom's N-th movie. Shom always makes the movies in order and does not make any other movies.

The first line contains a positive integer N. N is at most 10,000.

Print the N-th smallest doom number on the first line.