Description

Xiao D is a math enthusiast, and his obsession with numbers has reached a crazy level.

We use $d = \gcd(a, b)$ to denote the greatest common divisor of $a$ and $b$. Xiao D insists that such a close relationship can be described as parents. In this case, we call the ordered pair $(a, b)$ a parent pair of $d$.

Unlike normal parents, for the same $d$, it has too many parents.

For example, $(4, 6)$, $(6, 4)$, $(2, 100)$ are all parent pairs of $2$.
Thus the following question arises: for $1 \leq a \leq A$, $1 \leq b \leq B$, how many ordered pairs $(a, b)$ are parent pairs of $d$?

Input Format

The input contains a single line with three integers, representing $A$, $B$, and $d$.

Output Format

Output a single integer on one line representing the answer.

5 5 2

3

Hint

Sample 1 Explanation

There are three parent pairs: $(2, 2)$, $(2, 4)$, $(4, 2)$.

Constraints

• For $100\%$ of the testdata, it is guaranteed that $1 \leq A, B \leq 10^6$, $1 \leq d \leq \min(A, B)$.

Translated by ChatGPT 5