Multiplying by Rotation

Warning: Not all numbers in this problem are decimal numbers!

Multiplication of natural numbers in general is a cumbersome operation. In some cases, however, the product can be obtained by moving the last digit to the front.

Example: 179487 · 4 = 717948.

Of course, this property depends on the number system you use; in the above example, we used the decimal representation. In base 9, we have a shorter example:

17 · 4 = 71 (base 9)

as (1 · 9 + 7) · 4 = 7 · 9 + 1.

Input Specification

Each line of the input consists of three numbers, separated by a space: the base of the number system, the least significant digit of the first factor, and the second factor. This second factor is one-digit only, hence it is less than the base. All numbers in the input are given in decimal representation. The input ends with end-of-file (EOF).

Output Specification

For each input line, your program must determine the number of digits of the smallest first factor with the “rotamult” property. Each line of the output should contain the answer for the corresponding input line.

Sample Input

1. 10 7 4
2. 9 7 4
3. 17 14 12

download as text file

Output for Sample Input

1. 6
2. 2
3. 4

download as text file