MBR - Multiplying by Rotation

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 (9 * 1 + 7) * 4 = 7 * 9 + 1

Input

Each line consists of three numbers separated by a space: the base (<=36) of the number system, the least significant digit of the first factor, and the second factor. This second factor is one digit only hence less than the base. The input file ends with the standard end-of-file marker.

All Numbers in input are greater than 1 and will fit in the standard "int" data type. For base > 10 you can assume the digits to be 'A' ... 'Z'.

Note: Numbers in input may or may not be expressed using the above digits (refer example)

Output

Your program determines for each input line the number of digits of the smallest first factor with the rotamult property. Each line contains the answer for the corresponding input line.

Example

Input:
10 7 4
9 7 4
17 14 12
17 E C

Output:
6
2
4
4

The last two inputs are actually the same.


Added by:SALVO
Date:2010-05-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:UVA (own input)

hide comments
2013-12-14 19:35:12 Ankit Jain
basic knowlwdge about multiplication is enough to solve this problem...
2010-10-07 07:25:04 Prof_Utonium_ಉಮೆಶ್
This is similar to problem DOUBLE
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.