Взаємно прості#2725
Дано число . Потрібно підрахувати кількість цілих чисел у проміжку від до включно, які є взаємно простими з .
Два цілі числа називаються взаємно простими, якщо вони не мають спільних додатних дільників, окрім , або, іншими словами, якщо їхній найбільший спільний дільник дорівнює . Число є взаємно простим з будь-яким цілим числом.
Перший рядок містить (0 < T \leq 100) — кількість тестових випадків. Кожен з наступних рядків містить три цілі числа , , , де 1 \leq A \leq B \leq 10^{15} та 1 \leq N \leq 10^9.
Для кожного тесту виведіть кількість цілих чисел у проміжку від до включно, які є взаємно простими з .
Приклад 1