You have a fraction <image>. You need to find the first occurrence of digit c into decimal notation of the fraction after decimal point.

Input

The first contains three single positive integers a, b, c (1 ≤ a < b ≤ 105, 0 ≤ c ≤ 9).

Output

Print position of the first occurrence of digit c into the fraction. Positions are numbered from 1 after decimal point. It there is no such position, print -1.

Examples

Input

1 2 0


Output

2

Input

2 3 7


Output

-1

Note

The fraction in the first example has the following decimal notation: <image>. The first zero stands on second position.

The fraction in the second example has the following decimal notation: <image>. There is no digit 7 in decimal notation of the fraction. 
def fun(a, b, c):
    QR = []
    flag = 0
    t = 0
    while(flag == 0):
        t = t + 1
        qr = []
        q = int(a * 10 / b)
        r = a * 10 % b
        qr.append(q)
        qr.append(r)
        a = r
        if q == c:
            return t
        if qr in QR:
            flag == 1
            return -1
        QR.append(qr)
a, b, c = input("").split(" ", 2)
a = int(a)
b = int(b)
c = int(c)
print(fun(a, b, c))
    	 		  	 	 	  	  	    		 			