Hiếu rất yêu thích số nguyên tố, đồng thời cùng rất yêu thích số 5. Hiếu luôn coi các số nguyên tố có tổng các chừ số chia hết cho 5 là số đặc biệt. Lần này, thầy giáo đưa cho Hiếu 2 số nguyên dương $L,R(L\le R)$. Hiếu muốn biết trong đoạn $[L,R]$ có bao nhiêu số đặc biệt nên nhờ các bạn trả lời giúp.

Input

• Dòng đầu tiên chứa số nguyên dương $T(1\le T\le 100)$ là số lượng test trong file.
• $T$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương 𝐿,𝑅 (0<𝐿≤𝑅≤3×106)L,R (0<L≤R≤3×106) theo thứ tự, phân tách nhau bởi dấu cách.

Output

• Ghi ra $T$ dòng, mỗi dòng ghi một số là số lượng số đặc biệt trong đoạn $[L,R]$, tương ứng theo thứ tự trong file input. Dòng thứ $i$ trong file output là kết quả của cặp số $[L,R]$ ở dòng $i+1$ trong file input.

Example

Test 1

InputCopy2 1 10 4 20 OutputCopy1 2Note

13LikeComment(1)BookmarkShareReport
Recommended problems:

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

int check(int n){
    int s=0;
    while (n>0){
        s+=n%10;
        n/=10;
    }
    return s;
}
void sangnt(ll l,ll r){
	int x[r-l+1];
	int s=0;
	for(ll i=l;i<=r;i++){
		x[i-l] = 1;
	}
	for(ll i=2;i<=sqrt(r);i++){
		for(ll j=max(i*i,(l+i-1)/i*i);j<=r;j+=i){
			x[j-l] =0;
		}
	}
	for(ll i=max(2ll,l);i<= r;i++){
		if(x[i-l] && check(i)%5==0){
            s+=1;
		}
	}cout<<s;
}

int main(){
    ll T,s=0,l,r;
    cin>>T;
    for (int i=0;i<T;i++){
        cin>>l>>r;
        sangnt(l,r);
    }
    //meothinhle
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int t, l, r, ma[1000005], dem;
bool kt5(int n)
{
    int to = 0;
    while(n > 0)
    {
        to += n % 10;
        n /= 10;
    }
    return to % 5 == 0;
}
void sang()
{
    for(int a = 2; a <= 1000000; a++)
        ma[a] = 1;

    for(int a = 2; a * a <= 1000000; a++)
    {
        if(ma[a])
        {
            for(int b = a * a; b <= 1000000; b += a)
                ma[b] = 0;

            if(!kt5(a))
                ma[a] = 0;
        }
    }
}
int main()
{
    sang();
    cin >> t;
    while(t--)
    {
        cin >> l >> r;
        for(int i = l; i <= r; i++)
            if(ma[i]) dem++;
        cout << dem << "\n";
    }
    return 0;
}