Дано число ~N~. Вас просять порахувати кількість цілих чисел між ~A~ і ~B~ включно, які є взаємно простими з ~N~.

Два цілі числа називаються взаємно простими або взаємно простими, якщо вони не мають спільних додатних дільників, крім 1 або, еквівалентно, якщо їхній найбільший спільний дільник дорівнює 1. Число 1 є взаємно простим для кожного цілого числа.

Формат вхідних даних

Перший рядок містить ~T~ (~0 < T \le 100~) кількість тестів.

Кожен із наступних ~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

Пояснення

У першому тестовому випадку пʼять цілих чисел у діапазоні [1,10], які є відносно простими до 2, є {1,3,5,7,9}.