Даны два целых числа \(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\).
В первом наборе входных данных примера возможные значения \(x\) — это \([0, 1, 3, 4, 6, 7]\).
Во втором наборе входных данных единственное возможное значение \(x\) равно \(0\).
3 4 9 5 10 42 9999999967
6 1 9999999966
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач