You have a fraction $\frac{a}{b}$. 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 ≤ 10^5, 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: $\frac{1}{2} = 0.500(0)$. The first zero stands on second position.

The fraction in the second example has the following decimal notation: $\frac{2}{3} = 0.666(6)$. There is no digit 7 in decimal notation of the fraction.

Difficulty: interview

Starter code:

Solutions:
a, b, c = list(map(int, input().split()))

pos = 1
for i in range(1000000):
	d = (10 * a) // b
	a = (10 * a) % b
	if c == d:
		print(pos)
		return
	else:
		pos += 1
print(-1)

q,w,e=list(map(int,input().split()))
i=1
q*=10
while q//w!=e:
    q%=w
    q*=10
    i+=1
    
    if i>1000:
        i=-1
        break
print(i)


a, b, c = list(map(int, input().strip().split()))
a = a % b

for i in range(10*b):
    a *= 10
    d = a // b
    a = a % b
    # print(a, d)
    if c == d:
        print(i+1)
        break
else:
    print(-1)



a,b,c=[int(i) for i in input().split()]
d=0
while d<1000:
    d+=1
    if str(a*(10**d)//b)[-1]==str(c):
        print(d)
        return
print(-1)
    


from sys import stdin, stdout
from decimal import *

getcontext().prec = 1000

a,b,c = list(map(int,stdin.readline().rstrip().split()))
x = str(Decimal(a)/Decimal(b))[2:]

if len(x)==1000:
    x=x[:-1]
else:
    x = ''.join([x,'0'])
    
if str(c) in x:
    print(x.index(str(c))+1)
else:
    print(-1)



def main():
    a, b, c = map(int, input().split())
    a %= b
    a += b
    if a == 0:
        if c == 0:
            print(1)
        else:
            print(-1)
        return
    a = str(a * (10 ** 100000) // b)
    for i in range(1, len(a)):
        if int(a[i]) == c:
            print(i)
            return
    print(-1)


main()

a, b, c = map(int, input().split())
a %= b

k = 0
for i in range(1000):
    cf = 0
    while (cf < 9 and (k * 10 + cf + 1) * b <= a * 10):
        cf += 1
    
    if cf == c:
        print(i + 1)
        return
        
    k = k * 10 + cf
    a *= 10
        
        
print(-1)

a, b, c = list(map(int, input('').strip().split()))
occur = dict()
count = 0
for i in range(10 ** 6):
    count += 1
    a *= 10
    occurs = a // b
    occur[a] = occurs
    left = a % b
    if occurs == c:
        print(count)
        break
    else:
        if left * 10 in occur:
            print(-1)
            break
        else:
            a = a % b

a,b,c = map(int, input().split())
for i in range(2*b):
  a *= 10
  if a // b == c:
    print(i+1)
    break
  a %= b
else: print(-1)

import sys
a, b, c = list(map(int, input().split()))
if a // b:
    a %= b
p = 0
pp = [0] * 10
i = 0
while p < 10:   
    i += 1
    a %= b
    a *= 10     
    if i > 100000:
        break
    if a // b == c:
        print(i)
        return
    if pp[a // b] == 0:
        pp[a // b] = 1
        p += 1 
print(-1)
    


from decimal import *
getcontext().prec = 200000
[a, b, c] = list(map(int, input().split()))

q = b
while(q%2==0):
	q//=2
while(q%5==0):
	q//=5

ans = Decimal(a)/Decimal(b)
x = str(ans)
y = -1
p = 0
f = 0
g = 0
for u in x:
	if (f == 1):
		if (int(u) == c):
			y = p
			break
		p += 1
		if (p == b+1):
			g = 1
			break
	if (u == '.'):
		p = 1
		f = 1

if (c == 0):
	if (q == 1 and g == 0):
		y = p
print(y)


a, b, c = list(map(int, input().split()))

a %= b

visited = set()

result = -1
i = 1

while True:
    if a * 10 in visited:
        break
    visited.add(a * 10)
    tmp = (a * 10) // b
    if tmp == c:
        result = i
        break
    a = (a * 10) % b
    i += 1


print(result)


a, b, c = list(map(int, input().split()))
s = []
while a != 0:
    t = 0
    while a < b:
        if t == 1:
            s.append([0, 0])
            if c == 0:
                print(len(s))
                return
        a *= 10
        t = 1
    d = a // b
    a %= b
    if [d, a] in s:
        print(-1)
        return
    elif d == c:
        print(len(s) + 1)
        return
    s.append([d, a])
    if a == 0 and c == 0:
        print(len(s) + 1)
        return
print(-1)
        
    


V = set()
a, b, c = (int(i) for i in input().split())
i = 1
d = -1
shit = True
while a%b not in V:
    a = a%b
    V.add(a)
    a = a*10
    d = a//b
    if d == c:
        print(i)
        shit = False
        break
    i+=1
if shit:
    print(-1)   


arr=list(map(int,input().split()))
a=arr[0]
b=arr[1]
c=arr[2]
seq=[]
for i in range(0,2*b):
    seq.append((a*10)//b)
    a=(a*10)%b
if c in seq:
    print(seq.index(c)+1)
else:
    print(-1)    

from decimal import *
import math
getcontext().prec=100000
a,b,c = list(map(int,input().split()))
f = str(Decimal(a)/Decimal(b))
if len(f)<100000: f = f + '0'
suc = False
for i in range(2,10**5):
    if i == len(f): break
    if f[i] == str(c):
        print(i-1)
        suc = True
        break
if not suc: print(-1)


from decimal import *
a, b, c = map(int, input().split())
getcontext().prec = 100000
dec = Decimal(a) / Decimal(b)
t = -1
s = str(dec)
y = -1
for i in range(100000):
	st = "0"
	if (i < len(s)):
		st = s[i]
	if st == ".":
		y = i
	if st == str(c):
		if y >= 0:
			t = i - y
			break
print(t)

a,b,c=map(int,input().split())
a*=10**100000
a//=b
a=str(a)
while len(a)!=100000:
    a='0'+a
c=str(c)
if c in a:
    for i in range(100000):
        if a[i]==c:
            print(i+1)
            break
else:
    print(-1)

a, b, c = [int(x) for x in input().split(' ')]
a %= b
k = 0
for i in range(1, 10**4):
    a *= 10
    if (a//b) % 10 == c:
        print(i)
        k = 1
        break

if not k:
    print(-1)


from functools import lru_cache

a, b, c = tuple(map(int, input().split()))
a *= 10
k = 0
flag = True

while flag:
    k += 1

    d = a // b
    a = (a % b) * 10
    if c == d:
        flag = False
        print(k)


    if k> 100000:
        print(-1)
        flag = False


a,b,c=map(int,input().split())
s=set()
a*=10
i=1
while True:
    if c==(a//b):
        print(i)
        return
    a=(a-(a//b)*b)*10
    i+=1
    if i>150000:
        print(-1)
        return

a, b, c = list(map(int, input().split()))
pos = -1
for i in range(1, 309):
    if int((a * pow(10, i) // b)) % 10 == c:
        pos = i
        break
print(pos)

#128 7 0


a,b,c = list(map(int, input().split()))

used = set([a])
a *= 10
i = 1 
while True:
    if a//b == c:
        print(i)
        return
    a %= b
    if a in used:
        break
    used |= set([a])
    a *= 10
    i += 1
print(-1)
        


a, b, c = list(map(int, input().split()))
store = []
cnt = 1
while cnt < 1000:
    a = a * 10
    d = a // b
    store.append(d)
    a = a % b
    cnt += 1

pos = -111
try:
    pos = store.index(c)
except ValueError:
    pos = -1

print(pos if pos == -1 else pos + 1)


from fractions import Fraction

(a, b, c) = tuple(map(int, input().split()))
f = Fraction(a, b)
for i in range(900):
    for j in range(10):
        if f < Fraction(j+1, 10):
            if j == c:
                print(i+1)
                return
            f -= Fraction(j, 10)
            f *= 10
            break
print(-1)