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 java.util.*;

public class d {
  static boolean debug = false;
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in); 

    int numT = in.nextInt(); 
    for(int t=0; t<numT; t++) {
      long a = in.nextLong(); 
      long m = in.nextLong();

      long gcd = gcd(a, m);
      if(debug) System.out.printf("GCD = %d\n", gcd);

      ArrayList<Long> mFactors = factor(m);
      ArrayList<Long> gcdFactors = factor(gcd);
      
      if(debug) {
        System.out.println("gcd");
        for(int i=0; i<gcdFactors.size(); i++) {
          System.out.printf("%d ", gcdFactors.get(i));
        }
        System.out.println();
      }

      ArrayList<Long> multiplesToIgnore = new ArrayList();
      HashSet<Long> hs = new HashSet<>();
      int mFactorsInd = 0;
      for(int i=0; i<gcdFactors.size(); i++) {
        if(mFactorsInd >= mFactors.size()) break;
        long cur = gcdFactors.get(i);
        long mFactorsCur = mFactors.get(mFactorsInd);
        if(mFactorsCur == cur) {
          mFactorsInd++;
        } else {
          // else we skip the lower one.
          if(mFactorsCur < cur) {
            // Since we don't include it, we add it to the list
            if(!hs.contains(mFactorsCur)) {
              multiplesToIgnore.add(mFactorsCur); // only add unique
              hs.add(mFactorsCur);
            }
            mFactorsInd++;
            i--;
            continue;
          } else {
            // iterate through gcd list
            continue;
          }
        }
      }

      // Now we add any other ones we ignored
      for(int i=mFactorsInd; i<mFactors.size(); i++) {
        if(!hs.contains(mFactors.get(i))) {
          multiplesToIgnore.add(mFactors.get(i));
          hs.add(mFactors.get(i));
        }
      }

      if(debug) {
        System.out.println("FactorsToIgnore");
        for(int i=0; i<multiplesToIgnore.size(); i++) {
          System.out.printf("%d ", multiplesToIgnore.get(i));
        }
        System.out.println();
      }

      // We add every gcd-th value
      long ans = m/gcd;

      // Now we calculate the number of things to ignore.
      for(int bit=1 ; bit<(1<<multiplesToIgnore.size()); bit++) {
        int numOn = 0;
        long mult = 1;
        for(int i=0; i<multiplesToIgnore.size(); i++) {
          if((bit & (1<<i)) != 0) {
            numOn++;
            mult *= multiplesToIgnore.get(i);
          }
        }
        if(numOn%2 == 1) {
          ans -= (m/gcd)/mult;
        } else {
          ans += (m/gcd)/mult;
        }
      }
      System.out.println(ans);
    }
  }

  static ArrayList<Long> factor(long n) {
    ArrayList<Long> ans = new ArrayList<Long>();
    for(long x=2; x*x <= n; x++) {
      while(n%x == 0) {
        n/=x;
        ans.add(x);
      }
    }
    if(n != 1) ans.add(n); 
    return ans;
  }

  static long gcd(long a, long b) {
    return (b == 0) ? a : gcd(b, a%b);
  }
}