#P2183. 我要,我就要

我要,我就要

“我要吃麦当当,我就是要吃麦当当....”

“额,你如果能告诉我这个数n可以最少被多少个1组成的数整除,你就可以吃到麦当当了”

“...哼!我知道,答案是。。”

 

Input

多组测试数据
每次给你一个n,并保证n不能被2或者5整除,n是一个int范围内的数。

Output

输出能整除n这个由1组成的数中最少有多少个1。

Sample Input

3 
7 
9901

Sample Output

3
6
12

HINT

Source