Дано число \(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}.