cate

/*
Raluca Costineanu
cerinta 1 n * (nr patrate perfecte)
cerinta 2 ciur (pt 1000) cu sume partiale
*/
#include <bits/stdc++.h>

using namespace std;

ifstream f("cate.in");
ofstream g("cate.out");

int prime[1010];
int n, C, a, b;

int main()
{
    f>>C>>n;
    if(C==1)
    {
        int x, ra, rb;
        for(int i=1; i<=n; ++i)
        {
            f>>a>>b;
            if(a>b)
                x=a, a=b, b=x;
            ra=sqrt(a);
            rb=sqrt(b);
            if(ra*ra<a) ra++;
            g<<rb-ra+1<<'\n';
        }
    }
    else
    {
        int i, j, x, ra, rb;
        for(i=2; i<=1000; ++i)
            prime[i]=1;
        for(i=2; i<=31; ++i)
            for(j=i*i; j<=1000; j += i)
                prime[j]=0;
        for(i=1; i<=1000; ++i)
            prime[i]+=prime[i-1];
        for(int i=1; i<=n; ++i)
        {
            f>>a>>b;
            if(a>b)
                x=a, a=b, b=x;
            ra=sqrt(a);
            rb=sqrt(b);
            if(ra*ra<a) ra++;
            g<<prime[rb]-prime[ra-1]<<'\n';
        }
    }
    return 0;
}