描述
给定一个数 $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$ 互质的整数的个数。请按照下面的输出格式输出。
样例
- 复制
- 复制
关注我们
