#include <bits/stdc++.h>
//Here, we are solving the Prime Visits question
//We have to find number of prime numbers in the range a-b for each query
//So the optimised brute force approach is using prime sieve and cal number of prime b/w a and b for each query
//But this would be of the order O(Q.N), where N = b-a, and lets say if N = 10^6 and Q=1000
//Then order becomes 10^9 ====> TLE
 
//So optimised approach is to precompute the array of primes usinng prime sieve over a large range
//Take an array of cummulative sum that stores the count of prime numbers upto an index i
//Then number of prime numbrs in the a-b is given by csum[b] - csum[a-1]
//For this approach, Complexity is O(Q+N) N for prime sieve and Q for queries
 
 
using namespace std;
#define ll long long
 
void prime_sieve(int *p)
{
    p[0] = p[1] = 0; //0 and 1 are not primes
    p[2] = 1; //2 is a prime number
 
    //Now, we can skip all even numbers because they can never be prime
    //But, odd numbers can be potential prime numbers
    //Therefore, initially marking all odd numbers as 1
    for(ll i=3; i<=1000000; i+=2)
    {
        p[i] = 1;
    }
    //sieve approach
    for(ll i=3; i<=1000000; i+=2)
    {
        if(p[i])//current number is prime
        {
           for(ll j=i; j*i<=1000000; j++)
           {
               p[i*j] = 0;
           }
        }
    }
 
}
int main() {
    int p[1000005] = {0};
    prime_sieve(p);
 
    int csum[1000005] = {0};
    for(ll i=1; i<=1000000; i++)
    {
        csum[i] = csum[i-1] + p[i];
    }
 
    int q,a,b;
    cin>>q;
 
    while(q--)
    {
        cin>>a>>b;
        cout<<csum[b]-csum[a-1]<<"\n";
    }
 
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Ci8vSGVyZSwgd2UgYXJlIHNvbHZpbmcgdGhlIFByaW1lIFZpc2l0cyBxdWVzdGlvbgovL1dlIGhhdmUgdG8gZmluZCBudW1iZXIgb2YgcHJpbWUgbnVtYmVycyBpbiB0aGUgcmFuZ2UgYS1iIGZvciBlYWNoIHF1ZXJ5Ci8vU28gdGhlIG9wdGltaXNlZCBicnV0ZSBmb3JjZSBhcHByb2FjaCBpcyB1c2luZyBwcmltZSBzaWV2ZSBhbmQgY2FsIG51bWJlciBvZiBwcmltZSBiL3cgYSBhbmQgYiBmb3IgZWFjaCBxdWVyeQovL0J1dCB0aGlzIHdvdWxkIGJlIG9mIHRoZSBvcmRlciBPKFEuTiksIHdoZXJlIE4gPSBiLWEsIGFuZCBsZXRzIHNheSBpZiBOID0gMTBeNiBhbmQgUT0xMDAwCi8vVGhlbiBvcmRlciBiZWNvbWVzIDEwXjkgPT09PT4gVExFCgovL1NvIG9wdGltaXNlZCBhcHByb2FjaCBpcyB0byBwcmVjb21wdXRlIHRoZSBhcnJheSBvZiBwcmltZXMgdXNpbm5nIHByaW1lIHNpZXZlIG92ZXIgYSBsYXJnZSByYW5nZQovL1Rha2UgYW4gYXJyYXkgb2YgY3VtbXVsYXRpdmUgc3VtIHRoYXQgc3RvcmVzIHRoZSBjb3VudCBvZiBwcmltZSBudW1iZXJzIHVwdG8gYW4gaW5kZXggaQovL1RoZW4gbnVtYmVyIG9mIHByaW1lIG51bWJycyBpbiB0aGUgYS1iIGlzIGdpdmVuIGJ5IGNzdW1bYl0gLSBjc3VtW2EtMV0KLy9Gb3IgdGhpcyBhcHByb2FjaCwgQ29tcGxleGl0eSBpcyBPKFErTikgTiBmb3IgcHJpbWUgc2lldmUgYW5kIFEgZm9yIHF1ZXJpZXMKCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGxsIGxvbmcgbG9uZwoKdm9pZCBwcmltZV9zaWV2ZShpbnQgKnApCnsKICAgIHBbMF0gPSBwWzFdID0gMDsgLy8wIGFuZCAxIGFyZSBub3QgcHJpbWVzCiAgICBwWzJdID0gMTsgLy8yIGlzIGEgcHJpbWUgbnVtYmVyCgogICAgLy9Ob3csIHdlIGNhbiBza2lwIGFsbCBldmVuIG51bWJlcnMgYmVjYXVzZSB0aGV5IGNhbiBuZXZlciBiZSBwcmltZQogICAgLy9CdXQsIG9kZCBudW1iZXJzIGNhbiBiZSBwb3RlbnRpYWwgcHJpbWUgbnVtYmVycwogICAgLy9UaGVyZWZvcmUsIGluaXRpYWxseSBtYXJraW5nIGFsbCBvZGQgbnVtYmVycyBhcyAxCiAgICBmb3IobGwgaT0zOyBpPD0xMDAwMDAwOyBpKz0yKQogICAgewogICAgICAgIHBbaV0gPSAxOwogICAgfQogICAgLy9zaWV2ZSBhcHByb2FjaAogICAgZm9yKGxsIGk9MzsgaTw9MTAwMDAwMDsgaSs9MikKICAgIHsKICAgICAgICBpZihwW2ldKS8vY3VycmVudCBudW1iZXIgaXMgcHJpbWUKICAgICAgICB7CiAgICAgICAgICAgZm9yKGxsIGo9aTsgaippPD0xMDAwMDAwOyBqKyspCiAgICAgICAgICAgewogICAgICAgICAgICAgICBwW2kqal0gPSAwOwogICAgICAgICAgIH0KICAgICAgICB9CiAgICB9Cgp9CmludCBtYWluKCkgewogICAgaW50IHBbMTAwMDAwNV0gPSB7MH07CiAgICBwcmltZV9zaWV2ZShwKTsKCiAgICBpbnQgY3N1bVsxMDAwMDA1XSA9IHswfTsKICAgIGZvcihsbCBpPTE7IGk8PTEwMDAwMDA7IGkrKykKICAgIHsKICAgICAgICBjc3VtW2ldID0gY3N1bVtpLTFdICsgcFtpXTsKICAgIH0KCiAgICBpbnQgcSxhLGI7CiAgICBjaW4+PnE7CgogICAgd2hpbGUocS0tKQogICAgewogICAgICAgIGNpbj4+YT4+YjsKICAgICAgICBjb3V0PDxjc3VtW2JdLWNzdW1bYS0xXTw8IlxuIjsKICAgIH0KCiAgICByZXR1cm4gMDsKfQo=

MgoxIDEwCjExIDIw

2
1 10
11 20