题目描述

自从小 X 研究出了 BetaGo 之后，他发现数学是一门很重要的学科，在解决实际问题的时候经常会要用到一些数学知识。导致小 X 最近对数和数字比较感兴趣，而他喜欢把数拆成一位一位的数字来看，例如 $712839$ 在小 X 眼中就是 $1, 2, 3, 7, 8, 9$ 六个数字。

小 X 发现了一种完美数：如果在一个数中，$1$～$9$ 这 $9$ 种数字都出现至少一次，例如 $84376521931$ 这个数就很完美了。而如果缺了 $1$～$9$ 中的某一种时，这个数就不太完美，例如 $712839$ 中就缺了 $4, 5, 6$ 三种数字。

但是小 X 发现 $1$～$9$ 全出现在一个数中时，这个数会非常大。为了避免这种情况，小 X 想了一个好办法，那就是判断一个数 $n$ 是否完美时，不仅仅看这个数 $n$ 本身是否包含 $1$～$9$ 这 $9$ 种数字，同时去看这个数的倍数。也就是说如果这个数 $n$ 不完美，那就看 $n$ 和 $2n$ 两个数中是否包含了 $1$～$9$ 这 $9$ 种数字。如果还是没有，那就再看 $n$，$2n$，$3n$ 三个数中是否包含了 $1$～$9$ 这 $9$ 种数字，以此类推。

例如当 $n = 712839$ 时，这个数只包含了 $1, 2, 3, 7, 8, 9$，所以并不完美。

$2 \times n = 1425678$，那么 $n$ 中包含了 $1, 2, 3, 7, 8, 9$，而 $2 \times n$ 中又包含了 $1, 2, 4, 5, 6, 7, 8$，所以当我们数到 $2 \times n$ 时这个数就完美了。

小 X 想知道对于任意一个从键盘输入的数 $n$，需要数到多少时，这个数才完美。

输入格式

输入数据仅有一行包含一个正整数 $n$（$n \le 10^{10}$），表示小 X 想知道这个数 $n$ 需要数到多少时才完美。

输出格式

输出一行仅有一个数 $ans$，表示需要数到 $ans$ 这个数才完美，$ans = k \times n$（$k$ 为正整数）。（$ans \le 10^{18}$）

样例

1

9

312

1872

数据范围

• $n \le 10^{10}$
• $ans \le 10^{18}$

来源

市赛 数组问题