双亲数

时间限制:10s      空间限制:259MB

题目描述

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


输入格式

输入文件只有一行,三个正整数A、B、d (d <= A, B),意义如题所示。


输出格式

输出一行一个整数,给出满足条件的双亲数的个数。


样例输入



 


5 5 2
 

样例输出

 3


【样例解释】

满足条件的三对双亲数为(2, 2) (2, 4) (4, 2)

提示

对于100%的数据满足0 < A, B < 10^ 6


题目来源

第一届“NOIer”全国竞赛

Menuappsclose