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.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Scanner;

public class scratch_16{
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        long num= sc.nextLong();
        long den= sc.nextLong();
        long c= sc.nextLong();
        String d= String.valueOf(c);
        char e= d.charAt(0);
        String s= fractionToDecimal(num,den);
        long f= s.length();
        boolean b=false;
        for (int i = 2; i <f ; i++) {
            if (s.charAt(i) == e && !b) {
                System.out.println(i - 1);
                System.exit(0);
            } else if (s.charAt(i) == '(') {
                b = true;
            } else if (s.charAt(i) == e && b) {
                System.out.println(i - 2);
                System.exit(0);
            }
        }
       if(c==0 && !b){
           System.out.println(f-2+1);
       }
       else{
           System.out.println(-1);
       }




        }







    public static String fractionToDecimal(long numerator, long denominator) {
        if(denominator == 1)
            return String.valueOf(numerator);
        else if(denominator == -1)
            return String.valueOf(-(long)numerator);
        else if(denominator == 0)
            return "NaN";
        else{
            long quotient = 0, remainder;
            boolean positive = true;
            if(numerator > 0 && denominator < 0)
                positive = false;

            if(numerator < 0 && denominator > 0)
                positive = false;

            long N = Math.abs((long)numerator);
            long D = Math.abs((long)denominator);

            if(N > D){
                quotient = N / D;
            }

            remainder = N - (quotient * D);

            if(remainder == 0){
                if(!positive)
                    quotient = -quotient;

                return String.valueOf(quotient);
            }else{
                LinkedHashMap<Long, Long> map = new LinkedHashMap<Long, Long>();
                if(remainder < D){
                    remainder = remainder * 10;
                }

                while(remainder > 0){
                    if(map.containsKey(remainder))
                        break;
                    if(remainder < D){
                        map.put(remainder, 0L);
                        remainder = remainder * 10;
                    }else{
                        map.put(remainder, remainder / D);
                        remainder = remainder - ((remainder / D) * D);
                        if(remainder != 0){
                            remainder = remainder * 10;
                        }
                    }
                }

                long repeatMarker = remainder;

                StringBuilder result = new StringBuilder();
                StringBuilder recurringPattern = new StringBuilder();
                if(!positive){
                    result.append("-");
                }

                result.append(String.valueOf(quotient));

                if(map.size() > 0){
                    result.append("."); // decimal point
                }

                boolean repeatedMarkerSeen = false;
                for(long key : map.keySet()){
                    if(key == repeatMarker){
                        repeatedMarkerSeen = true;
                        recurringPattern.append(map.get(key));
                    }else{
                        if(repeatedMarkerSeen){
                            recurringPattern.append(map.get(key));
                        }else{
                            result.append(map.get(key));
                        }
                    }
                }

                if(recurringPattern.length() > 0){
                    result.append("(");
                    result.append(recurringPattern);
                    result.append(")");
                }

                return result.toString();
            }
        }
    }




}