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 ≤ 10¹⁶).

Output

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

Example

Input:
1001
500

Output:
91
250