2021 TS10 DANANG B3. Số đặc biệt

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 3000005

int n = 3000000, t;
int f[maxn];

int tongcs(int s) {
	int ans = 0;
	while(s > 0) {
		ans += s % 10;
		s /= 10;
	}
	return ans;
}

bool check_snt(int s) {
	for(int i = 2; i <= sqrt(s); i++)
        if(s % i == 0) return false;
	return true;
}

void giai() {
    for(int i = 1; i <= n; i++)
    {
        if(tongcs(i)%5==0&&check_snt(i)==true)
            f[i]=f[i-1]+1;
        else f[i]=f[i-1];
    }
    int l, r;
    cin >> t;
	for(int i=1;i<=t;i++){
		cin >> l >> r;
		cout << f[r] - f[l - 1] << endl;
	}
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("a.inp", "r", stdin);
    freopen("a.out", "w", stdout);
    giai();
}