牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在 $k$ 进制下，一个数的小数部分是纯循环的，那么它就是美的。

现在，牛牛想知道：对于已知的十进制数 $n$ 和 $m$，在 $k$ 进制下，有多少个数值上互不相等的纯循环小数，可以用分数 $\frac{x}{y}$ 表示,其中 $1\le x\le n,1\le y\le m$，且 $x,y$ 是整数。

一个数是纯循环的，当且仅当其可以写成以下形式：

$$a.\dot{c_1}{c}_2{c}_3\dots c_{p-1}\dot{c_p}$$

其中，$a$ 是一个整数，$p\ge 1$；对于 $1\le i\le p$，$c_i$ 是 $k$ 进制下的一位数字。

例如，在十进制下，$0.45454545\dots \dots =0.\dot{4}\dot{5}$是纯循环的，它可以用 $\frac{5}{11}$、$\frac{10}{22}$ 等分数表示；在十进制下，$0.1666666\dots \dots =0.1\dot{6}$则不是纯循环的，它可以用 $\frac{1}{6}$ 等分数表示。

需要特别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成 $0$ 的循环或是 $k-1$ 的循环；而一个小数部分非 $0$ 的有限小数不是纯循环的。

输入格式

输入文件只有一行，包含三个十进制数 $n,m,k$，意义如题所述。

输出格式

只输出一行一个整数，表示满足条件的美的数的个数。

样例一

input

2 6 10

output

4

explanation

满足条件的数分别是：

$$1/1=1.0000\dots \dots$$ $$1/3=0.3333\dots \dots$$ $$2/1=2.0000\dots \dots$$ $$2/3=0.6666\dots \dots$$

$1/1$ 和 $2/2$ 虽然都是纯循环小数，但因为它们相等，因此只计数一次；同样，$1/3$ 和 $2/6$ 也只计数一次。

样例二

input

23333 666666 310

output

5089564081

提示

这部分将提供一个将分数化为对应的小数的方法，如果你已经熟悉这个方法，你不必阅读本提示。

分数可以通过除法，用分子除以分母化为对应的小数。有些分数在除法过程中无法除尽,这样的分数在不断进行的除法过程中余数一定会重复出现。从商数的个位所对应的余数起，设第一次重复出现的余数前两次出现的位置所对应的商数位分别是小数点后第 $a$ 位和小数点后第 $b$ 位（特殊地：如果其中一个对应的商数位是个位，则认为 $a=0$；不妨设 $a<b$），则其循环部分可以用小数点后第 $a+1$ 位到小数点后第 $b$ 位的循环来表示。

例如：在十进制下，将 $\frac{5}{11}$ 转化为小数时，个位开始的商数依次为 $4,5,4,\dots$，对应的余数分别为 $6,5,6,\dots$。余数第一次重复出现的位置是个位和小数点后第 $2$ 位,那么 $a=0,b=2$ 即其循环部分可以用小数点第 $1$ 位到第 $3$ 位来表示。表示为：$\frac{5}{11}=0.45454545\dots =0.\dot{4}\dot{5}$。

在十进制下，将 $\frac{1}{6}$ 转化为小数时,个位开始的商数依次为 $1,6,6,\dots$，对应的余数分别为 $4,4,4,\dots$。余数第一次重复出现的位置是小数点后第 $1$ 位和小数点后第 $2$ 位,即其循环部分可以用小数点后第 $2$ 位来表示。表示为：$\frac{1}{6}=0.1666\dots \dots =0.1\dot{6}$。

需要注意的是：商数重复出现并不代表进入了循环节。

限制与约定

对于所有的测试点，保证 $1\le n\le {10}^9,1\le m\le {10}^9,2\le k\le 2000$。对于每个测试点，有以下约束（其中留空的表示没有特殊的约束）：

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载