시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 377 31 11 8.800%

문제

세 개의 정수 a, b, d가 주어지면, 다음의 세 조건을 만족하는 자연수 순서쌍 (x, y)의 개수를 구하는 프로그램을 작성하시오.

  1. 1 ≤ x ≤ a
  2. 1 ≤ y ≤ b
  3. x와 y의 최대공약수는 d이다.

입력

여러 개의 문제가 하나의 입력파일 내에 주어진다. 첫째 줄에 문제의 개수 n이 주어진다. 각각의 문제는 세 개의 정수 a, b, d로 이루어져 있다. 둘째 줄부터 한 줄에 한 문제씩, 문제를 나타내는 세 정수 a, b, d가 주어진다. n과 각각의 a, b, d는 모두 50,000 이하의 자연수이며, d는 a, b 이하이다.

출력

각 문제의 답을 한 줄에 하나씩 출력하도록 한다.

예제 입력

2
4 5 2
6 4 3

예제 출력

3
2

힌트

첫 번째 문제의 경우, (2,2), (2,4), (4,2) 세 개의 순서쌍이 존재한다. 두 번째 문제의 경우 (3,3), (6,3) 두 개의 순서쌍이 존재한다.