#include <iostream>
using namespace std;
int a[1000005];
bool b[1000005];
void pan_duan(int n)
{
    a[1] = 0;
    b[1] = true;
    for(int i = 2;i <= n;i++)
    {
        if(b[i] == false)
        {
            a[i] = a[i - 1] + 1;
            for(int j = i + i;j <= n;j = j + i)
                b[j] = true;
        }
        else
            a[i] = a[i - 1];
    }
}

int main()
{
    int n , m;
    cin >> n >> m;
    pan_duan(n);
    for(int i = 1;i <= m;i++)
    {
        int x , y;
        cin >> x >> y;
        if(x < 1 || y > n) 
            cout << "Crossing the line" << endl;
        else 
        {
            int sum = b[x] - b[y - 1];
            cout << sum << endl;
        }
    }
    return 0;
}