#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

int T, n, m;
void read(int &x)
{
  x = 0;
  char ch;
  while (!isdigit(ch = getchar()))
    ;
  while (isdigit(ch))
  {
    x = (x << 1) + (x << 3) + (ch ^ 48);
    ch = getchar();
  }
}
void print(int x)
{
  if (x < 0)
  {
    putchar('-');
    print(-x);
  }
  if (!x)
    return;
  print(x / 10);
  putchar(x % 10 + 48);
}
int factorCounter(int x)
{
  int cnt = 0;
  for (int i = 1; 1LL * i * i <= x; i++)
    if (x % i == 0)
    {
      cnt++;
      if (i * i != x)
        cnt++;
    }
  return cnt;
}

int main()
{
  read(T);
  while (T--)
  {
    read(n), read(m);
    int d = __gcd(n, m);
    int ans = factorCounter(n) - factorCounter(d);
    if (ans)
      print(ans);
    else
      putchar('0');
    putchar('\n');
  }
  return 0;
}