Counting Parent Pairs

Little D is fascinated by numbers. He believes that the intimate relationship between two numbers can be described by their greatest common divisor (gcd). For any two positive integers a and b, let \(d = \gcd(a,b)\). We say that the ordered pair \((a, b)\) is a parent pair of \(d\). For example, \((4,6)\), \((6,4)\) and \((2,100)\) are all parent pairs of \(2\).

Given three integers A, B and d, count how many ordered pairs \((a, b)\) satisfy \(1 \le a \le A\), \(1 \le b \le B\) such that \(\gcd(a,b) = d\). For convenience, note that if we let \(a=d \times x\) and \(b=d \times y\), the condition \(\gcd(a,b)=d\) is equivalent to \(\gcd(x,y)=1\) where \(1 \le x \le \lfloor A/d \rfloor\) and \(1 \le y \le \lfloor B/d \rfloor\).

The answer can be computed by evaluating the following summation:

[ \text{Answer} = \sum_{i=1}^{\min(\lfloor A/d \rfloor,\lfloor B/d \rfloor)} \mu(i) \left\lfloor \frac{\lfloor A/d \rfloor}{i} \right\rfloor \left\lfloor \frac{\lfloor B/d \rfloor}{i} \right\rfloor, ]

where \(\mu(i)\) is the Möbius function.

inputFormat

The input consists of a single line containing three integers A, B, and d (separated by spaces).

outputFormat

Output a single integer, the number of ordered pairs \((a, b)\) such that \(1 \le a \le A\), \(1 \le b \le B\) and \(\gcd(a,b)=d\).

sample

10 10 2

19