Juspay Hiring Process Round-2

Engineers are studying a signal with base level S and a cycle length M. They call an offset t stable if adding it to the base level doesn't change the signal's "common factor" with the cycle."

Formally, let g(x, y) denote the greatest common divisor of x and y. Count how many integers t satisfy:

0 ≤ t < M, and g(s, M) = g(s + t, M).

Input The first line contains an integer T (1 ≤ T ≤ 50) - the number of scenarios. Each of the next T lines contains two integers S and M (1 ≤ S < M < 10^10).

Output For each scenario, print a single integer - the number of stable offsets t.