You are given two integers a and m. Calculate the number of integers x such that 0 ≤ x < m and \gcd(a, m) = \gcd(a + x, m).

Note: \gcd(a, b) is the greatest common divisor of a and b.

Input

The first line contains the single integer T (1 ≤ T ≤ 50) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains two integers a and m (1 ≤ a < m ≤ 10^{10}).

Output

Print T integers — one per test case. For each test case print the number of appropriate x-s.

Example

Input


3
4 9
5 10
42 9999999967


Output


6
1
9999999966

Note

In the first test case appropriate x-s are [0, 1, 3, 4, 6, 7].

In the second test case the only appropriate x is 0.
import math
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()


def resolve():
    t = int(input())
    
    # https://www.geeksforgeeks.org/eulers-totient-function/
    # https://qiita.com/drken/items/a14e9af0ca2d857dad23#%E5%95%8F%E9%A1%8C-6-%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E9%96%A2%E6%95%B0
    # オイラー関数
    # 1,2,...,NのうちNと互いに素であるものの個数

    def euler_phi(n):

        # Initialize result as n
        result = n

        # Consider all prime factors
        # of n and subtract their
        # multiples from result
        p = 2
        while(p * p <= n):

            # Check if p is a
            # prime factor.
            if (n % p == 0):

                # If yes, then
                # update n and result
                while (n % p == 0):
                    n = int(n / p)
                result -= int(result / p)
            p += 1

        # If n has a prime factor
        # greater than sqrt(n)
        # (There can be at-most
        # one such prime factor)
        if (n > 1):
            result -= int(result / n)
        return result

    for i in range(t):
        a, m = map(int, input().split())
        g = math.gcd(a, m)
        mm = m//g
        print(euler_phi(mm))


resolve()