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

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

입력 형식

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

출력 형식

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

예제 입력

2
4 5 2
6 4 3

예제 출력

3
2

힌트

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