bedao_r03_kindness.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1000005;

int sieve[N], cnt[N], cnt2[10][N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  for (int i = 2; i < N; i++) {
    sieve[i] = 1;
  }
  for (int i = 2; i < N; i++) {
    if (!sieve[i]) continue;
    for (int j = i; j < N; j += i) {
      if (j != i) sieve[j] = 0;
      cnt[j] += 1;
    }
  }
  for (int i = 2; i < N; i++) {
    cnt2[cnt[i]][i]++;
    for (int j = 1; j <= 7; j++) {
      cnt2[j][i] += cnt2[j][i - 1];
    }
  }
  int q; cin >> q;
  while (q--) {
    int a, b, k;
    cin >> a >> b >> k;
    cout << cnt2[k][b] - cnt2[k][a - 1] << '\n';
  }
}