双亲数

题目描述

小 D 是一名数学爱好者,他对数字的着迷到了疯狂的程度。 我们以 $d = \gcd(a, b)$ 表示 $a, b$ 的最大公约数,小 D 执著的认为,这样亲密的关系足可以用双亲来描述,此时,我们称**有序**数对 $(a, b)$ 为 $d$ 的双亲数。 与正常双亲不太相同的是,对于同一个 $d$,他的双亲太多了。 比如,$(4, 6)$,$(6, 4)$,$(2, 100)$ 都是 $2$ 的双亲数。 于是一个这样的问题摆在眼前,对于 $1 \leq a \leq A$,$1 \leq b \leq B$,有多少**有序**数对 $(a, b)$ 是 $d$ 的双亲数?

输入输出格式

输入格式


输入只有一行三个整数,分别表示 $A, B, d$。

输出格式


输出一行一个整数表示答案。

输入输出样例

输入样例 #1

5 5 2

输出样例 #1

3

说明

#### 样例 1 解释 共有三对双亲数:$(2, 2)$,$(2, 4)$,$(4, 2)$。 #### 数据规模与约定 - 对于 $40\%$ 的数据,保证 $1 \leq A, B \leq 10^6$。 - 对于 $100\%$ 的数据,保证 $1 \leq A, B \leq 10^6$,$1 \leq d \leq \min(A, B)$。