Coding is the closest thing we have to superpower ！
描述
假设两个数 a,b 互质，那么 gcd(a,b)=1，没有除去 1 以外的公因子。
现在给你一个区间 [L,R] ，你需要求出这个区间与 n 互质的个数。
1与任何数都互质。
输入
输入第一行包括一个 T，测试数据个数。
接下来 T 行，每组测试用例包含三个数 L,R,n，含义如上。
输出
对于每个测试用例，打印 L 和 R 之间的与 n 互质的整数个数，遵循下面的输出格式。
样例
输入
2 1 10 2 3 15 5
输出
Case #1: 5 Case #2: 10
提示
任务点 #1：40分 0 < T ≤ 100,1 ≤ L ≤ R ≤ 10^4,1 ≤ n ≤ 10^4
任务点 #2：60分 0 < T ≤ 100,1 ≤ L ≤ R ≤ 10^{15},1 ≤ n ≤ 10^9
标签