SPRIME TS10 Da Nang 2021-2022

#define task "SPRIME"

#include <iostream>
#include <cstdio>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 3e6 + 5;

int q, cnt[N];
bool IsComposite[N];

void Read()
{
    cin >> q;
}

// TTổng các chữ số của v
int Sum(int v)
{
    int ans(0);

    while (v)
    {
        ans += v % 10;
        v /= 10;
    }

    return ans;
}

void Solve()
{
    for (int i = 2; i < N; ++i)
    {
        if (!IsComposite[i]) // Nếu i là số nguyên tố
        {
            if (Sum(i) % 5 == 0) // Nếu i là số đặc biệt
                cnt[i] = 1;

            for (int j = i; j < N; j += i)
                IsComposite[j] = 1;
        }
        cnt[i] += cnt[i - 1];
    }

    while (q--)
    {
        int l, r;
        cin >> l >> r;

        cout << cnt[r] - cnt[l - 1] << "\n";
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    Solve();
}