#include <bits/stdc++.h>
using namespace std;
long long int power(long long int x, long long int y) {
  if (y == 0) return 1;
  long long int d = power(x, y / 2) % 1000000007;
  if (y % 2 == 0)
    return (d * d) % 1000000007;
  else
    return (((x * d) % 1000000007) * d) % 1000000007;
}
long long int divmod(long long int num, long long int den) {
  return (num * (power(den, 1000000007 - 2))) % 1000000007;
}
int mobius[100001];
int mob(int x) {
  int cnt = 0;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      x = x / i;
      cnt++;
    }
    if (x % i == 0) {
      return 0;
    }
  }
  if (x > 1) {
    cnt++;
  }
  if (cnt & 1) return -1;
  return 1;
}
long long int nmod(long long int x) {
  return (x % 1000000007 + 1000000007) % 1000000007;
}
long long int fact[100001];
long long int ncr(long long int n, long long int r) {
  long long int num = fact[n];
  long long int den = fact[r] * fact[n - r];
  den %= 1000000007;
  return divmod(num, den);
}
long long int calc(long long int n, long long int k, long long int x) {
  n = n / x;
  n = n - k;
  if (n < 0) return 0;
  if (n == 0) return 1;
  return ncr(n + k - 1, k - 1);
}
void solve() {
  int n, k;
  scanf("%d", &n);
  scanf("%d", &k);
  vector<int> f;
  for (int i = 1; i * i <= n; i++) {
    if (i * i == n) {
      f.push_back(i);
      break;
    }
    if (n % i == 0) {
      f.push_back(i);
      f.push_back(n / i);
    }
  }
  long long int ans = 0;
  for (int i = 0; i < f.size(); i++) {
    if (mobius[f[i]] == 0) continue;
    ans = ans + mobius[f[i]] * calc(n, k, f[i]);
  }
  ans = nmod(ans);
  printf("%lld\n", ans);
}
int main() {
  fact[0] = 1;
  for (int i = 1; i <= 100000; i++) fact[i] = (i * fact[i - 1]) % 1000000007;
  mobius[1] = 1;
  for (int i = 2; i <= 100000; i++) {
    mobius[i] = mob(i);
  }
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) solve();
}
