We say a base- real number is *beautiful* if the decimal part of the real number is purely cyclic.

Now we want to know given base-10 numbers , how many **distinct** (in value) purely cyclic real numbers there are that can be represented by where , , and are integers.

A real number is said to be purely cyclic if and only if it can be written in the form of where is an (base-) integer, , and for , is a digit in base .

For example, under base 10, is purely cyclic and can be represented by or . Under base 10, is not purely cyclic but can be represented by fractions like .

Attention: an integer is purely cyclic since its decimal part can be written as repeating 0s or repeating s. A terminating decimal whose decimal part is non-zero is not considered to be purely cyclic.

Notes: In China, the repeating part of a repeating decimal is marked by one or two dots. In some countries, the repeating part is marked by a line above the repeating part.

#### Input Specification

The input consists of one line with three base-10 integers whose meanings are described in the problem description.

#### Output Specification

Output a line with an integer denoting the beautiful numbers satisfying all the constraints.

#### Sample Input 1

`2 6 10`

#### Sample Output 1

`4`

#### Explanation of Sample 1

The beautiful numbers are , , , . Even though and are both purely cyclic, they are equal in value so they are only counted once. Similarly, and should also be counted once.

#### Sample Input 2

`23333 666666 310`

#### Sample Output 2

`5089564081`

#### Constraints

For all test cases, , , .

Items left blank means there are **no special restrictions**.

Test case | |||
---|---|---|---|

1 | |||

2 | |||

3 | |||

4 | |||

5 | |||

6 | |||

7 | |||

8 | |||

9 | |||

10 | |||

11 | |||

12 | |||

13 | |||

14 | |||

15 | |||

16 | |||

17 | |||

18 | |||

19 | |||

20 | |||

21 | |||

22,23 | |||

24,25 |

## Comments