constexpr int MAXN = (int)1e6 + 1;
bool is_composite[MAXN];
int digit_sum[MAXN];
int partial_sum[MAXN];

digit_sum[1] = 1;
for (int i = 2; i < MAXN; ++i) {
  digit_sum[i] = digit_sum[i / 10] + i % 10;
  if (!is_composite[i] && (int64_t) i * i < MAXN) {
    for (int j = i * i; j < MAXN; j += i) {
      is_composite[j] = true;
    }
  }
  partial_sum[i] = partial_sum[i - 1] + (!is_composite[i] && !is_composite[digit_sum[i]]);
}
int queries;
in >> queries;
for (int query = 0; query < queries; ++query) {
  int l, r;
  in >> l >> r;
  out << partial_sum[r] - partial_sum[l - 1] << '\n';
}