Devil's Number

Ancient people believed that 666 was a devil's number. Furthermore, if the decimal representation of a number contains three consecutive sixes (i.e. 666), it is also considered a devil's number. For example, 666, 1666, 6663, 16666, 6660666, etc., are all devil's numbers.

In ancient texts, references such as "the X-th smallest devil's number" created inconvenience for researchers. Your task is to write a program which, given an integer X, outputs the X-th smallest devil's number.

Note: A number is considered a devil's number if and only if it contains the substring \(666\) in its decimal representation.

inputFormat

The input consists of a single integer X (1 ≤ X ≤ 10000), indicating that you need to find the X-th smallest devil's number.

outputFormat

Output the X-th smallest devil's number.

sample

1

666