2652 「POI2007 R1」查询 Queries

译自 POI 2007 Stage 1.「Zapytania」

给定正整数 $a,b,d$，找出满足以下条件的正整数对 $(x,y)$ 的个数： * $1 \le x \le a$ * $1 \le y \le b$ * $\gcd(x,y)=d$

第一行一个整数 $n (1 \le n \le 50\ 000)$，表示询问的个数。

接下来 $n$ 行每行三个整数 $a,b,d$,$(1 \le d \le a,b \le 50\ 000)$，表示询问。

输出 $n$ 行，表示 $n$ 组询问的答案。

第一组询问的三个正整数对分别为 $(2,2), (2,4), (4,2)$。 第二组询问的两个正整数对分别为 $(3,3), (6,3)$.