Solve the programming task below in a Python markdown code block.
Number of tanka

Wishing to die in the spring under the flowers

This is one of the famous tanka poems that Saigyo Hoshi wrote. Tanka is a type of waka poem that has been popular in Japan for a long time, and most of it consists of five phrases and thirty-one sounds of 5, 7, 5, 7, and 7.

By the way, the number 57577 consists of two types, 5 and 7. Such a positive integer whose decimal notation consists of exactly two types of numbers is called a tanka number. For example, 10, 12, 57577, 25252 are tanka numbers, but 5, 11, 123, 20180701 are not tanka songs.

A positive integer N is given. Find the Nth smallest tanka number.

Input

The input consists of up to 100 datasets. Each dataset is represented in the following format.

> N

The integer N satisfies 1 ≤ N ≤ 1018.

The end of the input is represented by a single zero line.

Output

For each dataset, output the Nth smallest tanka number on one line.

Sample Input


1
2
3
390
1124
1546
314159265358979323
0


Output for the Sample Input


Ten
12
13
2020
25252
57577
7744444777744474777777774774744777747477444774744744






Example

Input

1
2
3
390
1124
1546
314159265358979323
0


Output

10
12
13
2020
25252
57577
7744444777744474777777774774744777747477444774744744