#include <bits/stdc++.h>
using namespace std;
int mu[100010], lst[100010], can[100010], flag[100010], pr[100010];
const long long Mod = 1000000007LL;
long long fac[100010], inv[100010];
long long exp(int a, long long b, long long c) {
  long long ans = 1, num = a;
  while (b > 0) {
    if (b % 2 == 1) ans = ans * num % c;
    num = num * num % c;
    b >>= 1;
  }
  return ans;
}
long long cal(int n, int m) {
  if (n < m) return 0;
  long long ans = fac[n];
  ans = ans * inv[m] % Mod;
  ans = ans * inv[n - m] % Mod;
  return ans;
}
int main() {
  memset(flag, -1, sizeof(flag));
  fac[0] = 1;
  inv[0] = 1;
  for (int i = 1; i <= 100000; i++) {
    fac[i] = fac[i - 1] * i % Mod;
    inv[i] = exp(i, Mod - 2, Mod) * inv[i - 1] % Mod;
  }
  mu[1] = 1;
  int pcnt = 0;
  for (int i = 2; i <= 100000; i++) {
    if (flag[i]) {
      pr[pcnt++] = i;
      lst[i] = i;
      mu[i] = -1;
    }
    for (int j = 0; j < pcnt && pr[j] <= 100000 / i; j++) {
      flag[i * pr[j]] = 0;
      if (lst[i] == pr[j]) {
        mu[i * pr[j]] = 0;
        break;
      }
      mu[i * pr[j]] = -mu[i];
      lst[i * pr[j]] = pr[j];
    }
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    long long ans = 0;
    for (int j = 1; j <= x / j; j++) {
      if (x % j != 0) continue;
      if (x / j == j) {
        if (mu[j]) ans += cal(j - 1, y - 1) * mu[j];
      } else {
        if (mu[x / j]) ans += cal(j - 1, y - 1) * mu[x / j];
        if (mu[j]) ans += cal(x / j - 1, y - 1) * mu[j];
      }
      ans %= Mod;
    }
    printf("%I64d\n", (ans + Mod) % Mod);
  }
  return 0;
}
