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.
''' Hey stalker :) '''
INF = 10**10
def main():
    print = out.append
    ''' Cook your dish here! '''
    a, b = get_list()
    print(phi(b//math.gcd(a,b)))


def 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

''' Pythonista fLite 1.1 '''
import sys
#from collections import defaultdict, Counter
#from bisect import bisect_left, bisect_right
#from functools import reduce
import math
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
out = []
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
#main()
[main() for _ in range(int(input()))]
print(*out, sep='\n')
