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.Scanner;
public class Position_in_Fraction_900B
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		int r=a%b;
		int pos = -1, curr=0, q;
		int s[] = new int[1000], s_pos=0;
		loop:
		while(r>0||c==0)
		{
			a = r*10;
			q = a/b;
			r = a%b;
			curr++;
			if(q==c)
			{
				pos=curr;
				break;
			}
			for(int i=0;i<s_pos;i++)
				if(s[i]==r)
					break loop;
			s[s_pos] = r;
			s_pos++;
		}
		System.out.println(pos);
	}

}
