AT_abc443_f [ABC443F] Non-Increasing Number

A positive integer $ X $ is called a **good integer** if and only if it satisfies the following condition: - When $ X $ is written in decimal notation, the ones digit, tens digit, $ \ldots $ form a non-increasing sequence. - More formally, the unique non-negative integer sequence $ (d_0,d_1,\ldots) $ satisfying $ \displaystyle X=\sum_{i=0}^{\infty} d_i10^i $ $ (0\le d_i < 10) $ forms a non-increasing sequence. For example, $ 112389 $ , $ 1 $ , and $ 777 $ are good integers, but $ 443 $ and $ 404 $ are not good integers. You are given a positive integer $ N $ . Determine whether there exists a good integer that is a multiple of $ N $ , and if it exists, find its minimum value.

The input is given from Standard Input in the following format: > $ N $

If there does not exist a good integer that is a multiple of $ N $ , output $ -1 $ . If it exists, output the minimum value of a good integer that is a multiple of $ N $ .

### Sample Explanation 1 $ 126 $ is a multiple of $ 21 $ , and we have $ 6 \geq 2 \geq 1 \geq 0 \geq \ldots $ , so it is a good integer. There does not exist a good integer less than $ 126 $ that is a multiple of $ 21 $ , so output $ 126 $ . ### Sample Explanation 4 The answer may be $ 2^{64} $ or greater. ### Constraints - $ 1\le N\le 3\times 10^6 $ - All input values are integers.