900_B. Position in Fraction_28704
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.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.TreeSet;

import static java.lang.Math.abs;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.util.Arrays.copyOf;
import static java.util.Arrays.fill;
import static java.util.Arrays.sort;
import static java.util.Collections.reverseOrder;
import static java.util.Collections.sort;

public class Main {
    private FastScanner in;
    private PrintWriter out;

    private void solve() throws IOException {
        solveB();
    }

    private void solveA() throws IOException {
        int n = in.nextInt(), l = 0, r = 0, x, y;
        for (int i = 0; i < n; i++) {
            x = in.nextInt();
            y = in.nextInt();
            if (x > 0)
                r++;
            else
                l++;
        }
        out.println(l < 2 || r < 2 ? "Yes" : "No");
    }

    private void solveB() throws IOException {
        long a = in.nextLong(), b = in.nextLong(), c = in.nextLong(), cur, hash, cnt = 0;
        HashSet<Long> set = new HashSet<>();
        while (true) {
            a *= 10;
            cur = a / b;
            a %= b;
            hash = cur * 1000000 + a;
            cnt++;
            if (set.contains(hash)) {
                out.println(-1);
                return;
            } else if (cur == c) {
                out.println(cnt);
                return;
            } else {
                set.add(hash);
            }
        }

    }

    private void solveC() throws IOException {

    }

    private void solveD() throws IOException {

    }

    private void solveE() throws IOException {

    }

    class FastScanner {
        StringTokenizer st;
        BufferedReader br;

        FastScanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        boolean hasNext() throws IOException {
            return br.ready() || (st != null && st.hasMoreTokens());
        }

        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        String nextLine() throws IOException {
            return br.readLine();
        }

        boolean hasNextLine() throws IOException {
            return br.ready();
        }
    }

    private void run() throws IOException {
        in = new FastScanner(System.in); // new FastScanner(new FileInputStream(".in"));
        out = new PrintWriter(System.out); // new PrintWriter(new FileOutputStream(".out"));
        solve();
        out.flush();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }
}

2 3 7
 1 2 0
 1 10 1
 53 101 6
 567 1580 0
 69168 84860 4
 35 111 4
 99971 99989 0
 25102 31579 2
 13805 15538 3
 38790 39359 0
 2 3 0
 7 31 3
 1 9 0
 45 97 0
 1636 3269 6
 8 51 0
 1 3 0
 8880 81608 9
 1 7 7
 1 100 0
 1 100000 1
 1 57 0
 1 7 0
 1 2 5
 1 10001 9
 6873 7769 3
 4942 62768 5
 47117 78718 0
 99999 100000 8
 971 1883 3
 10958 21926 3
 44102 73848 2
 1 4 1
 69168 84860 8
 25102 57486 2
 13805 16262 3
 38790 64660 0
 7 30 3
 45 151 0
 1636 3269 9
 16 51 0
 13512 21926 3
 1 4 0
 1636 4367 9
 17650 21926 3
 558 1580 2
 8880 76242 0
 558 2062 3
 53 101 12
 567 1580 1
 35 111 8
 1 12 0
 8880 81608 0
 1 8 7
 1 57 1
 2 7 0
 1 11001 9
 433 7769 3
 47117 69358 0
 99999 100000 13
 971 1434 3
 1 3 7
 1 2 1
 558 1580 1
 69168 84860 1
 10757 57486 2
 10 30 3
 45 215 0
 13 51 0
 1 3 1
 8880 52919 0
 2 8 7
 1 22 1
 4 7 0
 367 7769 3
 47117 137344 0
 1649 100000 13
 627 1434 3
 1 3 5
 1 2 2
 2 4 0
 69168 84860 0
 10757 57486 4
 8 30 3
 68 215 0
 1636 4367 4
 13 65 0
 1 6 1
 2 14 7
 367 1552 3
 1649 100000 11
 778 1434 3
 1 2 3
 558 2062 2
 69168 103222 0
 8 23 3
 47 215 0
 1636 7762 4
 1 9 1
 14075 76242 0
 2 14 2
 367 1552 6
 778 1180 3
 50383 103222 0
 8 23 2
 47 215 1
 1 9 2
 14075 127808 0
 2 14 4
 367 3003 6
 778 1180 0

-1
 2
 1
 -1
 6
 107
 -1
 9
 174
 164
 212
 -1
 15
 -1
 39
 150
 10
 -1
 161
 6
 1
 5
 1
 -1
 1
 5
 163
 122
 213
 -1
 130
 117
 132
 -1
 1
 6
 20
 5
 2
 4
 10
 9
 41
 3
 8
 7
 12
 29
 22
 -1
 -1
 -1
 1
 2
 -1
 2
 -1
 5
 5
 6
 -1
 -1
 -1
 -1
 4
 2
 5
 1
 2
 5
 -1
 5
 -1
 -1
 -1
 5
 4
 -1
 2
 -1
 -1
 2
 4
 10
 -1
 7
 3
 2
 1
 6
 2
 -1
 5
 -1
 1
 3
 1
 5
 7
 1
 5
 3
 3
 4
 5
 5
 2
 -1
 3
 2
 -1
 7
