问题 4623 --互质的个数

4623: 互质的个数

时间限制: 1 Sec  内存限制: 128 MB
提交: 41  解决: 18
[提交][状态][命题人:]

题目描述

 求 [A,B]区间内，有多少个数，与N互质？ 

输入

第一行输入一个数 T(0<T<=100) ，表示数据组数。

每组数据包含三个整数 A,B,N ，其中 1<=A<=B<=10^15，1<=N<=10^9 。

输出

对于每组数据，输出一行结果。

格式如样例所示。

样例输入
Copy
2
1 10 2
3 15 5
样例输出
Copy
Case #1: 5
Case #2: 10

提示

来源

xinjun 

[提交][状态]