Pure Repeating Decimals

Cowboy Niuniu is a high school student who loves algorithm design. In many of his algorithms he uses numbers with decimals. He considers a number "beautiful" if, when represented in base \(k\), its decimal part is purely repeating. A number is defined as purely repeating if and only if it can be written in the following form:

[ a.\dot{c_1} c_2 c_3 \dots c_{p-1} \dot{c_p} ]

Here, \(a\) is an integer and \(p \ge 1\); for \(1 \le i \le p\), each \(c_i\) is a single digit in base \(k\). For example, in decimal (i.e. base 10), 0.45454545… = 0.\dot{4}\dot{5} is purely repeating since its repeating block starts immediately, and it can be represented by fractions such as \(\frac{5}{11}\) and \(\frac{10}{22}\). However, 0.1666666… = 0.1\dot{6} is not considered purely repeating because it has a non-repeating part before the repeating block. Note that we regard an integer as purely repeating since its decimal part may be represented as a repeating 0 sequence (or a repeating \(k-1\) sequence), while a terminating decimal with a nonzero fractional part is not.

Niuniu now wonders: Given two positive integers \(n\) and \(m\) (both given in decimal) and a base \(k\), how many distinct real numbers can be represented as a fraction \(\frac{x}{y}\) with \(1 \le x \le n\) and \(1 \le y \le m\) (where \(x\) and \(y\) are positive integers) that have a purely repeating representation in base \(k\)?

inputFormat

The input consists of a single line containing three space-separated integers \(n\), \(m\), and \(k\).

outputFormat

Output a single integer representing the count of distinct rational numbers that, when expressed in their lowest terms as \(\frac{x}{y}\) (with \(1 \le x \le n\) and \(1 \le y \le m\)), have a purely repeating expansion in base \(k\).
Note that an integer (when \(y=1\)) is considered to have a purely repeating presentation.

sample

5 5 10

9