//prewritten code: https://github.com/antma/algo
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.traits;
import std.bitmanip;
import std.typecons;
import std.numeric;

final class PrimeTable {
  private:
  BitArray a;
  size_t n;
  public:
  pure nothrow @nogc
  bool isPrime (size_t i) const {
    return (i & 1) ? !a[i>>>1] : (i == 2);
  }
  pure
  int[] primes () const {
    int[] p;
    if (n > 2) {
      p ~= 2;
      p ~= (~a).bitsSet.map! (i => (2 * i + 1).to!int).array;
    }
    return p;
  }
  pure
  this (size_t _n) {
    n = _n;
    auto m = n >> 1;
    a.length = max (1, m);
    a[0] = true;
    foreach (i; 1 .. ceil((sqrt (n.to!(double)) - 1.0)).to!(size_t)) {
      if (!a[i]) {
        immutable k = (i << 1) + 1;
        for (size_t j = 2 * i * (i + 1); j < m; j += k) {
          a[j] = true;
        }
      }
    }
  }
}

alias Factorization = Tuple!(ulong, "p", uint, "c")[];

pure
Factorization factorizationTrialDivision (ulong x, in int[] primes) in {
  assert (primes.takeExactly (2).equal ([2, 3]));
} body {
  Factorization f;
  foreach (p; chain (primes, iota (primes.back + 2, int.max, 2))) {
    if (p.to!ulong * p > x) {
      break;
    }
    uint c;
    while (!(x % p)) {
      x /= p;
      ++c;
    }
    if (c) {
      f ~= tuple!("p", "c")(p.to!ulong, c);
    }
  }
  if (x > 1) {
    f ~= tuple!("p", "c")(x, 1U);
  }
  return f;
}

final class InputReader {
  private:
  ubyte[] p, buffer;
  bool eof;
  bool rawRead () {
    if (eof) {
      return false;
    }
    p = stdin.rawRead (buffer);
    if (p.empty) {
      eof = true;
      return false;
    }
    return true;
  }
  ubyte nextByte(bool check) () {
    static if (check) {
      if (p.empty) {
        if (!rawRead ()) {
          return 0;
        }
      }
    }
    auto r = p.front;
    p.popFront ();
    return r;
  }
  public:
  this () {
    buffer = uninitializedArray!(ubyte[])(16<<20);
  }
  bool seekByte (in ubyte lo) {
    while (true) {
      p = p.find! (c => c >= lo);
      if (!p.empty) {
        return false;
      }
      if (!rawRead ()) {
        return true;
      }
    }
  }
  template next(T) if (isSigned!T) {
    T next ()  {
      if (seekByte (45)) {
        return 0;
      }
      T res;
      ubyte b = nextByte!false ();
      if (b == 45) {
        while (true) {
          b = nextByte!true ();
          if (b < 48 || b >= 58) {
            return res;
          }
          res = res * 10 - (b - 48);
        }
      } else {
        res = b - 48;
        while (true) {
          b = nextByte!true ();
          if (b < 48 || b >= 58) {
            return res;
          }
          res = res * 10 + (b - 48);
        }
      }
    }
  }
  template next(T) if (isUnsigned!T) {
    T next () {
      if (seekByte (48)) {
        return 0;
      }
      T res = nextByte!false () - 48;
      while (true) {
        ubyte b = nextByte!true ();
        if (b < 48 || b >= 58) {
          break;
        }
        res = res * 10 + (b - 48);
      }
      return res;
    }
  }
  T[] nextA(T) (in int n) {
    auto a = uninitializedArray!(T[]) (n);
    foreach (i; 0 .. n) {
      a[i] = next!T;
    }
    return a;
  }
}

long test (const ulong a, const ulong m, in int[] p) {
  long g = gcd (a, m);
  long m1 = m / g;
  auto f = factorizationTrialDivision (m1, p);
  immutable l = f.length.to!int;
  long cnt (const long x) {
    immutable t = x / g;
    long res;
    void go (int k, int sign, long x) {
      if (x > t) return;
      if (k < 0) {
        res += sign * (t / x);
      } else {
        go (k - 1, sign, x);
        go (k - 1, -sign, x * f[k].p);
      }
    }
    go (l - 1, 1, 1L);
    return res;
  }
  return cnt (a + m - 1) - cnt (a - 1);
}

int[] primes () {
  auto pt = new PrimeTable (110_000);
  return pt.primes ();
}

void main() {
  auto p = primes ();

  auto r = new InputReader ();
  immutable nt = r.next!uint ();
  foreach (tid; 0 .. nt) {
    immutable a = r.next!ulong;
    immutable m = r.next!ulong;
    writeln (test (a, m, p));
  }
}

