Взаємно прості

Дано число N. Ваше завдання — підрахувати кількість цілих чисел у проміжку від 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 включно, які є взаємно простими з N. Дотримуйтесь формату виводу, наведеного нижче.

Приклади