Counting GCD Pairs

A cryptographer is trying to break a cipher called BSA. In the process, he faces an additional challenge:

Given three integers \(a\), \(b\), and \(d\), count the number of ordered pairs \((x, y)\) such that \(1 \le x \le a\), \(1 \le y \le b\), and \(\gcd(x, y) = d\).

Note that if we substitute \(x = d \cdot u\) and \(y = d \cdot v\), the condition \(\gcd(x, y) = d\) becomes \(\gcd(u, v) = 1\) with \(1 \le u \le \lfloor a/d \rfloor\) and \(1 \le v \le \lfloor b/d \rfloor\). Your task is to compute the required number of pairs.

inputFormat

The input consists of a single line containing three space-separated integers \(a\), \(b\), and \(d\).

Constraints (for example):

• 1 \(\le a, b \le 10^5\)
• 1 \(\le d \le \min(a, b)\)

outputFormat

Output a single integer: the number of pairs \((x, y)\) such that \(1 \le x \le a\), \(1 \le y \le b\), and \(\gcd(x, y) = d\).

sample

10 5 1

35