#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void chkmax(T &x, T y) {
  if (x < y) x = y;
}
template <class T>
inline void chkmin(T &x, T y) {
  if (x > y) x = y;
}
int q, n, f, inv[100100], fac[100100], p[6];
void Euclid(int a, int b, int &x, int &y) {
  if (!a)
    x = 0, y = 1;
  else {
    int q = b / a, r = b % a;
    Euclid(r, a, y, x);
    x -= q * y;
  }
}
int cal(int n, int m) {
  if (m > n) return 0;
  return 1ll * fac[n - 1] * inv[m - 1] % 1000000007 * inv[n - m] % 1000000007;
}
int main() {
  fac[0] = 1;
  for (int i = 1; i < 100100; i++) fac[i] = 1ll * fac[i - 1] * i % 1000000007;
  int x, y;
  Euclid(fac[100100 - 1], 1000000007, x, y);
  inv[100100 - 1] = x;
  for (int i = 100100 - 1; i > 0; i--)
    inv[i - 1] = 1ll * inv[i] * i % 1000000007;
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d", &n, &f);
    x = 0, y = n;
    for (int i = 2; i <= sqrt(y); i++) {
      if (y % i) continue;
      p[x++] = i;
      while (y % i == 0) y /= i;
    }
    if (y > 1) p[x++] = y;
    y = 0;
    for (int i = 0; i < (1 << x); i++) {
      int tmp = n, cnt = 0;
      for (int j = 0; j < x; j++)
        if (i & (1 << j)) cnt++, tmp /= p[j];
      if (cnt & 1)
        y = (y - cal(tmp, f) + 1000000007) % 1000000007;
      else
        y = (y + cal(tmp, f)) % 1000000007;
    }
    printf("%d\n", y);
  }
  return 0;
}
