https://vjudge.net/problem/HDU-4135

请原谅我没有弄LaTeX

题目描述

给定一个数N，你需要计算在A和B之间（包括A和B）有多少个整数与N互质。 如果两个整数没有除1以外的公约数，即最大公约数为1，则它们被称为互质。数字1与任何整数都是互质的。

输入格式

输入的第一行包含T（0 < T <= 100），表示测试用例的数量，接下来的T行每行包含三个整数A、B、N，其中（1 <= A <= B <= 10^15）和（1 <= N <= 10^9）。

输出格式

对于每个测试用例，输出A和B之间（包括A和B）与N互质的整数的数量。请按照以下格式输出。

样例

2
1 10 2
3 15 5

Case #1: 5
Case #2: 10

解释

在第一个测试用例中，范围[1,10]内与2互质的五个整数是{1,3,5,7,9}。