서로소

자연수 $N$이 주어졌을 때, $A$ 이상 $B$ 이하인 수 중에서 $N$과 서로소인 것이 몇 개인지 세는 프로그램을 작성하시오.

두 정수를 모두 나누는 양의 정수가 1뿐이면 두 정수를 서로소라고 한다. 즉 두 수의 최대공약수가 1이면 서로소이다. 1은 모든 정수와 서로소이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($0 < T \le 100$)

각 테스트 케이스는 한 줄로 이루어지며, 세 정수 $A$, $B$, $N$이 공백으로 구분되어 주어진다. ($1 \le A \le B \le 10^{15}$, $1 \le N \le 10^9$)

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $A$ 이상 $B$ 이하인 자연수 중에서 $N$과 서로소인 것의 개수이다.

$[1, 10]$에 속하는 수 중에서 2와 서로소인 것은 $1, 3, 5, 7, 9$이다.