Đếm bộ bốn theo UCLN

Cho ba số nguyên \(L\), \(R\), \(K\). Hãy đếm số bộ có thứ tự bốn số nguyên \((x, y, u, v)\) thoả mãn:

• \(L \le x, y, u, v \le R\);
• ước chung lớn nhất \(\gcd(x, y, u, v)\) đúng bằng \(K\).

Hai bộ khác nhau nếu khác nhau ở ít nhất một vị trí (ví dụ \((1,2,2,2)\) và \((2,1,2,2)\) là hai bộ khác nhau).

Input

• Một dòng gồm ba số nguyên \(L\), \(R\), \(K\).

Output

• In ra số bộ thoả mãn.

Constraints

• \(1 \le L \le R \le 5000\).
• \(1 \le K \le 5000\).

Sample Input 1

1 6 2

Sample Output 1

79

Sample Input 2

4 30 4

Sample Output 2

2303

Explanation

Ở ví dụ 1 các số phải là bội của \(2\) trong \([1, 6]\), tức thuộc \(\{2, 4, 6\}\); chia cho \(2\) được các số trong \(\{1, 2, 3\}\) có \(\gcd = 1\). Có \(3^4 = 81\) bộ, trừ đi \(2\) bộ có \(\gcd\) lớn hơn \(1\) (bộ toàn số \(2\) và bộ toàn số \(3\)) còn \(79\).