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. 
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a, b, c, r;
  scanf("%d", &a);
  scanf("%d", &b);
  scanf("%d", &c);
  if (a % b == 0) {
    if (c == 0)
      printf("%d\n", 1);
    else
      printf("%d\n", -1);
  } else {
    map<int, bool> make_pair;
    int i = 1;
    for (r = a % b; r != 0; r %= b) {
      if (make_pair[r] == 1) {
        printf("%d\n", -1);
        return 0;
      }
      make_pair[r] = 1;
      r *= 10;
      if ((r / b) == c) {
        printf("%d\n", i);
        return 0;
      }
      i++;
    }
    if (r == 0 && c)
      printf("%d\n", -1);
    else
      printf("%d\n", i);
  }
}
