Tanka Number

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

inputFormat

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.

outputFormat

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

样例

1
2
3
390
1124
1546
314159265358979323
0

10
12
13
2020
25252
57577
7744444777744474777777774774744777747477444774744744

</p>