Niu Niu is a high school student who loves algorithm design. In the algorithms he designs, he often uses numbers with decimal parts for calculations. Niu Niu believes that if the decimal part of a number in base $k$ is purely periodic, then it is beautiful.

Now, Niu Niu wants to know: for given decimal integers $n$ and $m$, how many numerically distinct purely periodic decimals in base $k$ can be represented as a fraction $\frac{x}{y}$, where $1 \le x \le n$, $1 \le y \le m$, and $x, y$ are integers.

A number is purely periodic if and only if it can be written in the following form: $$a.\dot{c}_1c_2c_3 \dots c_{p-1}\dot{c}_p$$ where $a$ is an integer, $p \ge 1$; for $1 \le i \le p$, $c_i$ is a digit in base $k$.

For example, in base 10, $0.45454545 \dots = 0.\dot{4}\dot{5}$ is purely periodic, and it can be represented by fractions such as $\frac{5}{11}$ and $\frac{10}{22}$. In base 10, $0.1666666 \dots = 0.1\dot{6}$ is not purely periodic, and it can be represented by the fraction $\frac{1}{6}$.

It is worth noting that we consider an integer to be purely periodic because its decimal part can be represented as a cycle of $0$ or a cycle of $k-1$; a finite decimal with a non-zero decimal part is not purely periodic.

Input

The input file is cyclic.in. The input file contains only one line, which includes three decimal positive integers $n, m, k$, with meanings as described above.

Output

The output file is cyclic.out. Output a single integer representing the number of beautiful numbers that satisfy the conditions.

Examples

Input 1

2 6 10

Output 1

4

Note 1

The fractions satisfying the conditions are: $1/1 = 1.0000 \dots$ $1/3 = 0.3333 \dots$ $2/1 = 2.0000 \dots$ $2/3 = 0.6666 \dots$ Although $1/1$ and $2/2$ are both purely periodic decimals, they are equal, so they are counted only once; similarly, $1/3$ and $2/6$ are counted only once.

Input 2

23333 666666 310

Output 2

5089564081

Note

This section provides a method for converting a fraction into its corresponding decimal. If you are already familiar with this method, you do not need to read this note.

A fraction can be converted into its corresponding decimal by dividing the numerator by the denominator. Some fractions cannot be divided exactly, and in such cases, the remainder will inevitably repeat during the continuous division process. Starting from the remainder corresponding to the integer part of the quotient, let the positions of the quotient digits corresponding to the first two occurrences of the repeating remainder be the $a$-th decimal place and the $b$-th decimal place (specifically: if one of the corresponding quotient digits is the integer part, we consider $a=0$; assume $a < b$), then its periodic part can be represented by the cycle from the $(a+1)$-th decimal place to the $b$-th decimal place.

For example, in base 10, when converting $\frac{5}{11}$ to a decimal, the quotient digits starting from the integer part are $4, 5, 4, \dots$, and the corresponding remainders are $6, 5, 6, \dots$. The remainder first repeats at the integer part and the 2nd decimal place, so $a=0, b=2$, meaning its periodic part can be represented by the cycle from the 1st to the 3rd decimal place, represented as: $\frac{5}{11} = 0.45454545 \dots = 0.\dot{4}\dot{5}$.

In base 10, when converting $\frac{1}{6}$ to a decimal, the quotient digits starting from the integer part are $1, 6, 6, \dots$, and the corresponding remainders are $4, 4, 4, \dots$. The remainder first repeats at the 1st decimal place and the 2nd decimal place, so its periodic part can be represented by the cycle from the 2nd decimal place. Represented as: $\frac{1}{6} = 0.1666 \dots = 0.1\dot{6}$.

Note that the repetition of a quotient digit does not necessarily mean the start of a periodic cycle.

Subtasks

For all test cases, it is guaranteed that $1 \le n \le 10^9, 1 \le m \le 10^9, 2 \le k \le 2000$. For each test case, there are the following constraints (empty cells indicate no special constraints):