Ones

Given any integer 0 ≤ n ≤ 10,000 not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1's. How many digits are in the smallest such multiple of n?

Input File: ones.in

A file of integers at one integer per line.

Output File: ones.out

Each output line gives the smallest integer x > 0 such that p = ∑( i = 0 to x-1) 1 * 10ⁱ where a is the corresponding input integer, p = a * b and b is an integer greater than zero.

Sample Input

3
7
9901

Sample Output

3
6
12