자연수 N이 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 수 중에서 N과 서로소인 것의 개수를 구하는 프로그램을 작성하시오.

두 정수를 나눌 수 있는 양의 정수가 1밖에 없을 때, 두 정수를 서로소라고 한다. 즉, 두 수의 최대공약수가 1이면 서로소이다. 1은 모든 정수와 서로소이다.

입력 형식

첫째 줄에 테스트 케이스의 개수 T (0 < T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, A, B, N이 주어진다. (1 ≤ A ≤ B ≤ 10¹⁵, 1 ≤ N ≤ 10⁹)

출력 형식

각 테스트 케이스마다 A보다 크거나 같고, B보다 작거나 같은 자연수 중에서 N과 서로소인 것의 개수를 출력한다. 

예제 입력

2
1 10 2
3 15 5

예제 출력

Case #1: 5
Case #2: 10

힌트

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