The Next Year with Distinct Digits

Interview

Time limit1sMemory limit128 MB

Summary

Given a year Y, print the smallest year greater than Y whose decimal digits are all distinct.

Level: Easy3 of 10
Topics: Brute force, Implementation
Solved: No attempts yet

Problem

2013 is the first year since 1987 in which all digits are distinct. The years 2014, 2015, 2016, 2017, 2018, and 2019 also have all distinct digits. The year 2012, however, does not, because the digit 2 appears twice.

Given a year $Y$ , find the earliest year greater than $Y$ in which every digit is distinct.

Input

The first line contains a single integer $Y$ , the starting year. ( $0 \le Y \le 10000$ )

Output

Print the earliest year $D$ greater than $Y$ in which every digit is distinct.

Examples5

Example 1
Input
```
1987
```
Expected output
```
2013
```
Example 2
Input
```
0
```
Expected output
```
1
```
Example 3
Input
```
8
```
Expected output
```
9
```
Example 4
Input
```
9
```
Expected output
```
10
```
Example 5
Input
```
6789
```
Expected output
```
6790
```