Stable

Problem Statement

Stable Problem Given two integers A and M , a shift x is called stable if: gcd(A + x, M) = gcd(A, M) The count is taken over one complete residue system modulo M (for example, 0 <= x < 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 , with 1 <= A < M <= 10^10 . Output For each scenario, print a single integer — the number of stable shifts x . Examples Example 1 Input: 1 643 671 Output: 600 Explanation: There are 600 stable shifts for A = 643 and M = 671. Example 2 Input: 1 817 860 Output: 8 Explanation: There are 8 stable shifts for A = 817 and M = 860. Sample test block 1 Input: 5 920 986 139 690 482 766 710 891 470 612 Output: 448 176 382 540 96 Explanation: One output line per scenario. Sample test block 2 Input: 8 1373 8395 7289 9593 8113 8542 5893 6005 8246 9239 9824 9850 4976 7211 9574 9808 Output: 6336 9360 4270 4800 9238 3920 7210 2448 Explanation: One output