Invariant

Problem Preview

"### 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."