Tomo's Calculator

The most advanced feature of Tomo's old calculator is that after multiplying two numbers, pressing the = button again keeps multiplying the displayed number by the second number that was entered. For example, if Tomo multiplies 2 and 3, the display shows 6. Each further press of = then shows 18, 54, 162, and so on.

Tomo wants to know how many times the = button must be pressed in total until a given number C appears as a suffix of the number on the display.

More precisely, Tomo enters a number A, presses *, enters a number B, and presses =. The product A times B appears on the display, and this first press of = is included in the count. If the displayed number does not end with C, Tomo keeps pressing = until the displayed number ends with C.

A number X is a suffix of a number Y if the decimal representation of Y ends with the decimal representation of X. For example, 46 is a suffix of 1246, but 70 is not a suffix of 4701. Assume that the calculator can handle arbitrarily many digits and can display all of them.

Given A, B, and C, compute the total number of times the = button is pressed.

The only line contains integers A, B, and C.

0 <= A, C <= 100000, and 0 <= B <= 1000. The decimal representation of C has no leading zeros.

Print one line containing the total number of times the = button is pressed. If C never becomes a suffix of the displayed number, print NIKAD.