Next Unique-Digit Number

Interview

Time limit1sMemory limit256 MB

Summary

Find the smallest integer above N that uses no zero and repeats none of the digits 1 to 9, printing 0 when none exists.

Level: Medium5 of 10
Topics: Backtracking, Combinatorics, Brute force
Solved: No attempts yet

Problem

A unique-digit number uses each digit from 1 to 9 at most once and never uses 0. Examples include 9, 32, 489, 98761, and 983245. Such numbers have at most 9 digits.

Given an integer $N$ , print the smallest unique-digit number strictly greater than $N$ . If no such number exists, print 0.

Input

The input has several test cases. Each test case is one line with an integer $N$ ( $0 \le N \le 999,999,999$ ).

Output

For each test case, print the answer on its own line. Print 0 when no valid number exists.

Examples4

Example 1
Input
```
99
881
133
999999999
```
Expected output
```
123
891
134
0
```
Example 2
Input
```
0
```
Expected output
```
1
```
Example 3
Input
```
9
```
Expected output
```
12
```
Example 4
Input
```
987654320
```
Expected output
```
987654321
```