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

Now we want to know given base-10 numbers $n,m$, how many distinct (in value) purely cyclic real numbers there are that can be represented by $\frac{x}{y}$ where $1\le x\le n$, $1\le y\le m$, and $x,y$ are integers.

A real number is said to be purely cyclic if and only if it can be written in the form of $${\displaystyle a.\dot{c_1}{c}_2{c}_3\dots c_{p-1}\dot{c_p}}$$ where $a$ is an (base-$k$) integer, $p\ge 1$, and for $1\le i\le p$, $c_i$ is a digit in base $k$.

For example, under base 10, $${\displaystyle 0.45454545\cdots =0.\dot{4}\dot{5}}$$ is purely cyclic and can be represented by $\frac{5}{11}$ or $\frac{10}{22}$. Under base 10, $${\displaystyle 0.166666\cdots =0.1\dot{6}}$$ is not purely cyclic but can be represented by fractions like $\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 whose decimal part is non-zero is not considered to be purely cyclic.

Notes: In China, the repeating part of a repeating decimal is marked by one or two dots. In some countries, the repeating part is marked by a line above the repeating part.

Input Specification

The input consists of one line with three base-10 integers $n,m,k$ whose meanings are described in the problem description.

Output Specification

Output a line with an integer denoting the beautiful numbers satisfying all the constraints.

Sample Input 1

2 6 10

Sample Output 1

4

Explanation of Sample 1

The beautiful numbers are $1/1=1.0000\dots$, $1/3=0.3333\dots$, $2/1=2.0000\dots$, $2/3=0.6666\dots$. Even though $1/1$ and $2/2$ are both purely cyclic, they are equal in value so they are only counted once. Similarly, $1/3$ and $2/6$ should also be counted once.

Sample Input 2

23333 666666 310

Sample Output 2

5089564081

Constraints

For all test cases, $1\le n\le {10}^9$, $1\le m\le {10}^9$, $2\le k\le 2000$.

Items left blank means there are no special restrictions.

Test case	$n$	$m$	$k$
1	$\le 10$	$\le 20$	$=2$
2	$\le 100$	$\le {10}^4$
3	$\le 1000$
4	$\le 10000$
5	$\le 10$	$\le 20$	$=3$
6	$\le 100$	$\le {10}^4$
7	$\le 1000$
8	$\le 10000$
9	$\le 10$	$\le 20$	$\le 100$
10	$\le 100$	$\le {10}^4$
11	$\le 1000$		$\le 1000$
12	$\le 10000$
13	$\le {10}^5$	$\le {10}^8$	$\le 100$
14	$\le 2\times {10}^5$		$\le 1000$
15	$\le 5\times {10}^5$
16	$\le {10}^6$	$\le {10}^8$	$\le 100$
17	$\le 2\times {10}^6$		$\le 1000$
18	$\le 5\times {10}^6$
19	$\le {10}^7$	$\le {10}^8$	$\le 100$
20	$\le 2\times {10}^7$		$\le 1000$
21
22,23	$\le {10}^8$	$\le {10}^8$
24,25