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\dots = 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\dots = 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 1\,000~
4	~\le 10\,000~
5	~\le 10~	~\le 20~	~=3~
6	~\le 100~	~\le 10^4~
7	~\le 1\,000~
8	~\le 10\,000~
9	~\le 10~	~\le 20~	~\le 100~
10	~\le 100~	~\le 10^4~
11	~\le 1\,000~		~\le 1\,000~
12	~\le 10\,000~
13	~\le 10^5~	~\le 10^8~	~\le 100~
14	~\le 2 \times 10^5~		~\le 1\,000~
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 1\,000~
21
22,23	~\le 10^8~	~\le 10^8~
24,25