CS - Another Longest Common Subsequence Problem

no tags 

Given a non-negative integer X. Calculate the smallest non-negative integer Y, such that Y <= X, and the length of the longest common subsequence (not necessarily continuous) of string(Y) and string(X-Y) is maximum possible, where string(T) denotes the decimal notation of number T without any leading zeroes.

Input

Multiple test cases. Each test case contains one line with one integer X (0 <= X <= 1016).

Output

For each test case output one line with one integer Y.

Example

Input:
1001
500

Output:
91
250


Added by:Fudan University Problem Setters
Date:2008-12-07
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own Problem