최대공약수가 정해진 순서쌍의 개수

세 정수 a, b, d가 주어진다. 다음 조건을 모두 만족하는 자연수 순서쌍 (x, y)의 개수를 구하라.

1. 1 <= x <= a
2. 1 <= y <= b
3. gcd(x, y) = d

하나의 입력 파일에 여러 질의가 주어진다. 첫째 줄에는 질의의 개수 N이 주어진다. 이어지는 N개의 줄에는 각 질의를 나타내는 세 정수 a, b, d가 주어진다.

각 질의의 답을 한 줄에 하나씩 출력한다.

• 1 <= N <= 50,000
• 1 <= a, b, d <= 50,000
• d <= a
• d <= b

공개 테스트의 첫 번째 질의에서는 (2, 2), (2, 4), (4, 2) 세 개의 순서쌍이 있다. 두 번째 질의에서는 (3, 3), (6, 3) 두 개의 순서쌍이 있다.