## CS - Another Longest Common Subsequence Problem

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^{16}).

### Output

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

### Example

Input:1001 500Output: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 |