给定一个数 N，请你计算在闭区间 [A, B] 内有多少个整数与 N 互质。
两个整数被称为互质（或相对素），如果它们除了 1 以外没有其他公共正因子，等价地说，它们的最大公约数为 1。数字 1 与所有整数都互质。
第一行包含一个整数 T，表示测试用例的数量。
接下来的 T 行，每行包含三个整数 A、B 和 N，其中 1 \le A \le B \le 10^{15}，1 \le N \le 10^9。
对于每个测试用例，输出在闭区间 [A, B] 内与 N 互质的整数的个数。请按照下面的输出格式输出。
2 1 10 2 3 15 5
Case #1: 5 Case #2: 10