Numbers With No Repeated Digits

Interview

Time limit1sMemory limit128 MB

Summary

Given n up to one million, print the n-th positive integer whose decimal digits are all distinct.

Level: Medium4 of 10
Topics: Brute force, Dynamic programming, Math
Solved: No attempts yet

Problem

Ever since he was young, Hanshin has loved numbers, but he strongly dislikes using the same digit more than once. So the only numbers Hanshin likes are the positive integers whose digits are all different from one another.

If you ask Hanshin to write these numbers in increasing order, the first 25 of them look like this:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 25, 26, 27, …

(Numbers that repeat a digit, such as 11 or 22, are skipped.)

Given an integer $n$ , write a program that finds the $n$ -th number in this sequence.

Input

The input consists of several test cases. Each line contains one integer $n$ ( $1 \le n \le 10^6$ ). Input ends at a line containing $n = 0$ , which is not processed.

Output

For each test case, print on its own line the $n$ -th number among the positive integers whose digits are all distinct, listed in increasing order.

Examples5

Example 1
Input
```
25
10000
0
```
Expected output
```
27
26057
```
Example 2
Input
```
1
0
```
Expected output
```
1
```
Example 3
Input
```
9
10
11
0
```
Expected output
```
9
10
12
```
Example 4
Input
```
90
91
0
```
Expected output
```
98
102
```

Example 5

Input

Expected output