Взаимно простые

Дано число 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. Следуйте формату вывода, приведенному ниже.

Примеры