#include <bits/stdc++.h>
const int mo = 1000000007;
const int MAX = 100000;
using namespace std;
int p[100005], ny[100005], Hash[100005];
int ss[100005][30], n, f, q, i, j, ans;
int sumi(int a, int b) {
  int ret = 1, c = a;
  while (b) {
    if (b & 1) ret = (long long)ret * c % mo;
    c = (long long)c * c % mo;
    b >>= 1;
  }
  return ret;
}
int C(int n, int m) {
  if (n < m) return 0;
  return (long long)p[n] * ny[m] % mo * ny[n - m] % mo;
}
void dfs(int i, int s, int odd) {
  if (i > ss[n][0]) {
    if (odd)
      ans -= C(n / s - 1, f - 1);
    else
      ans += C(n / s - 1, f - 1);
    ans %= mo;
    return;
  }
  dfs(i + 1, s, odd);
  dfs(i + 1, s * ss[n][i], 1 - odd);
}
int main() {
  for (i = 2; i <= MAX; i++) {
    if (Hash[i]) continue;
    ss[i][++ss[i][0]] = i;
    for (j = i + i; j <= MAX; j += i) {
      ss[j][++ss[j][0]] = i;
      Hash[j] = 1;
    }
  }
  p[0] = ny[0] = 1;
  for (i = 1; i <= MAX; i++) {
    p[i] = (long long)p[i - 1] * i % mo;
    ny[i] = (long long)ny[i - 1] * sumi(i, mo - 2) % mo;
  }
  scanf("%d", &q);
  while (q--) {
    scanf("%d %d", &n, &f);
    if (n == 1) {
      printf("1\n");
      continue;
    }
    ans = 0;
    dfs(1, 1, 0);
    while (ans < 0) ans += mo;
    printf("%d\n", ans);
  }
  return 0;
}
