Given three positive integers $n$, $m$, and $k$, count the number of infinitely repeating pure decimals that can be represented by the fraction:

$$\frac{x}{y}$$

where $1 \leq x \leq n$, $1 \leq y \leq m$, and $x$, $y$ are integers.

A real number is an infinitely repeating pure decimal if it can be written in the form $a.\overline{c_1c_2c_3\ldots c_{p-1}c_p}$ where $a$ is an integer, and $c_i$ are the digits in base $k$.

For example, in the decimal system, $0.45454545\ldots = 0.\overline{45}$ is an infinitely repeating pure decimal because it can be represented by fractions such as $\frac{5}{11}$, $\frac{10}{22},\ldots$

However, in the decimal system, $0.1666\ldots=0.1\overline{6}$ is not an infinitely repeating pure decimal as it cannot be represented by the fraction $\frac{1}{6}$.

Input

• One line containing three positive integers $n$, $m$, $k$.

Output

• Output a single integer, the answer.

Example

Input:

2 6 10

Output:

4

Explanation:

• There are $4$ numbers:
  • $\frac{1}{1}=1.\overline{0}$
  • $\frac{1}{3}=0.\overline{3}$
  • $\frac{2}{1}=2.\overline{0}$
  • $\frac{2}{3}=0.\overline{6}$

Input 2:

23333 666666 310

Output 2:

5089564081

Constraints

In each test case:

• $1 \le T \le 10, 1 \le n \le 30000$.