Stable

Problem Statement

Stable You are given two integers A and M . A shift x is called stable if gcd(A + x, M) = gcd(A, M) Count the stable shifts x with 0 <= x < M (inferred -- the source frame showing the range of x is unreadable; every sample answer matches one full residue system modulo M , 0 <= x < M ) . You have to answer T independent scenarios. Function description Complete the function solve with the following parameters: long A : the starting value long M : the modulus Returns long : the number of stable shifts x with 0 <= x < M . Input format The first line contains the integer T , the number of scenarios. Each of the next T lines contains two integers A and M . Output format For each scenario print the number of stable shifts on its own line. Constraints 1 <= T <= 50 1 <= A < M <= 10^10 Examples Example 1 Input: 1 643 671 Output: 600 Explanation: gcd(643, 671) = 1 , so a shift is stable when 643 + x is coprime to 671 = 11 * 61 . Among any 671 consecutive integers,