Stable

Problem Statement

Stable Problem Description Consider two integers A and M. A shift x is stable if: 0 ≤ x gcd(A, M) = gcd(A + x, M). Find the number of stable shifts for given values of A and 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 A and M (1 ≤ A M ≤ 10 10 ). Output For each scenario, print a single integer - the number of stable shifts x. Examples Example 1: Input: A = 643, M = 671 Output: 600 Example 2: Input: A = 817, M = 860 Output: 8 Example 3: Input: A = 920, M = 986 Output: 448 Example 4: Input: A = 139, M = 690 Output: 176 Constraints 1 ≤ T ≤ 50 1 ≤ A 10