Tomo's Calculator

Interview

Time limit1sMemory limit128 MB

Summary

Given a calculator that repeatedly multiplies by B starting from A*B, find how many presses of '=' are needed until the displayed number ends with a given suffix C, or report impossible.

Level: Medium5 of 10
Topics: Math, Simulation, Number theory
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1
Input
```
2 3 4
```
Expected output
```
3
```
Example 2
Input
```
1 2 3
```
Expected output
```
NIKAD
```
Example 3
Input
```
5 3 215
```
Expected output
```
5
```