ACM 2003 Test tour - As simple as it gets

Problem A. As simple as it gets ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	A. Klenin	Time limit:	1 sec
Input file:	input.txt	Memory limit:	64 Mb
Output file:	output.txt

Statement

Let us define that a positive integer A is simpler than a positive integer B if the decimal representation of A requires less different digits than the decimal representation of B.

For example, number 55 is simpler than 12 which in turn is simpler than 123.

Your program will be given a number N and must find the largest integer X such that X < N and X is simpler than N.

Input file format

Input file contains integer N.

Output file format

Output file must contain integer X. If there is no integer simpler than N, output file must contain 0 (zero).

Constraints

1 ≤ N ≤ 2³¹ − 1

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`111`	`0`
2	`765437654`	`765377777`