The Beauty of Cycles

We say a base-$k$ real number is beautiful if its decimal part is purely cyclic.

Given base-10 integers $n$ and $m$, count the distinct (in value) purely cyclic real numbers that can be written as $\frac{x}{y}$, where $x$ and $y$ are integers with $1 \leq x \leq n$ and $1 \leq y \leq m$.

A real number is purely cyclic if and only if it can be written in the form $\displaystyle a.\dot{c\_1} c\_2 c\_3 \ldots c\_{p-1} \dot{c\_p}$ where $a$ is a base-$k$ integer, $p \geq 1$, and for each $1 \leq i \leq p$, $c\_i$ is a base-$k$ digit.

For example, in base 10, $0.45454545\cdots = 0.\dot{4}\dot{5}$ is purely cyclic and can be represented by $\frac{5}{11}$ or $\frac{10}{22}$. In base 10, $0.166666\cdots = 0.1\dot{6}$ is not purely cyclic, but it can be represented by fractions such as $\frac{1}{6}$.

Attention: an integer is purely cyclic, since its decimal part can be written as repeating 0s or repeating $k-1$s. A terminating decimal with a nonzero decimal part is not purely cyclic.

In China, the repeating part is marked by one or two dots. In some countries, it is marked by a line above the repeating part.

The input is one line with three base-10 integers $n$, $m$, and $k$. Their meanings are described in the problem statement.

Print one line with the number of beautiful numbers that satisfy all the constraints.

For all test cases, $1 \leq n \leq 10^9$, $1 \leq m \leq 10^9$, and $2 \leq k \leq 2000$.