题目描述

已知自然数 $K$ ，若存在自然数 $M$ 和 $N$ （ $M>N$ ），使得 $K^M$ 和 $K^N$ 均大于或等于 $1000$，且它们的末三位数相等，则称 $M$ 和 $N$ 是一对“ $K$ 尾相等数”请编写一个程序，输出 $M+N$ 值最小的 $K$尾相等数。

输入格式

输入多组数据，每组一个 $K$ 。

输出格式

输出满足条件中的最小的 $M+N$ 的值，每组数据一行。

样例输入输出

样例输入

2

样例输出

120

数据范围

对于 $100%$ 的数据，保证 $1 \le K \le 100$ 。