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. 
import java.io.*;
import java.util.*;
import java.math.*;
public class PositionInFraction
{
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        char c=sc.next().charAt(0);
        BigDecimal x=BigDecimal.valueOf(a);
        BigDecimal y=BigDecimal.valueOf(b);
        String s=String.valueOf(x.divide(y,1000,RoundingMode.CEILING));
        int ans=-1,pos=0;
        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i)=='.')
            {
                pos=i;
                break;
            }
        }
        String e=s.substring(pos+1,s.length()-1);
        if(e.contains(String.valueOf(c)))
        {
            for(int i=0;i<e.length();i++)
            {
                if(e.charAt(i)==c)
                {
                    ans=i+1;
                    break;
                }
            }
            System.out.println(ans);
        }
        else    
            System.out.println(-1);
    }
}