D. Одинаковые GCD
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два целых числа $$$a$$$ и $$$m$$$. Посчитайте количество таких целых чисел $$$x$$$, что $$$0 \le x < m$$$ и $$$\gcd(a, m) = \gcd(a + x, m)$$$.

$$$\gcd(a, b)$$$ в данной задаче обозначает наибольший общий делитель $$$a$$$ и $$$b$$$.

Входные данные

В первой строке задано одно целое число $$$T$$$ ($$$1 \le T \le 50$$$) — количество наборов входных данных.

Следующие $$$T$$$ строк содержат наборы входных данных, по одному в каждой строке. Каждая строка содержит два целых числа $$$a$$$ и $$$m$$$ ($$$1 \le a < m \le 10^{10}$$$).

Выходные данные

Выведите $$$T$$$ целых чисел — по одному на каждый набор входных данных. Для каждого набора выведите количество подходящих чисел $$$x$$$.

Пример
Входные данные
3
4 9
5 10
42 9999999967
Выходные данные
6
1
9999999966
Примечание

В первом наборе входных данных примера возможные значения $$$x$$$ — это $$$[0, 1, 3, 4, 6, 7]$$$.

Во втором наборе входных данных единственное возможное значение $$$x$$$ равно $$$0$$$.