#126. Zap

Zap

题目描述

每组询问给出 a、b、d,统计 1≤x≤a、1≤y≤b 且 gcd(x,y)=d 的有序整数对数量。

输入格式

首行询问数,随后每行 a、b、d,1≤d≤a,b≤50000。

输出格式

每个询问输出一行计数。

样例输入

2
4 5 2
6 4 3

样例输出

3
2

题意整理;原题与输入输出格式对照。