from math import *
prime = [1] * (10 ** 6 + 1 )
def sang():
    prime[0] = 0
    prime[1] = 0
    for i in range(2 , isqrt((10 ** 6 + 1 )) + 1):
        if(prime[i]):
            for j in range(i * i , (10 ** 6 + 1 ), i):
                prime[j] = 0
 
if __name__ == '__main__':
    sang()
    F = [0] * (10 ** 6 + 1 )
    F[0] = 0
    F[1] = 0
    dem = 0
    for i in range(2 , (10 ** 6 + 1 )):
        if(prime[i]):
            dem += 1
        F[i] = dem
    t = int(input())
    for i in range(t):
        l , r = map(int , input().split())
        if(l == 0):
            print(F[r])
        else :
            print(F[r] - F[l - 1])
 

ZnJvbSBtYXRoIGltcG9ydCAqCnByaW1lID0gWzFdICogKDEwICoqIDYgKyAxICkKZGVmIHNhbmcoKToKICAgIHByaW1lWzBdID0gMAogICAgcHJpbWVbMV0gPSAwCiAgICBmb3IgaSBpbiByYW5nZSgyICwgaXNxcnQoKDEwICoqIDYgKyAxICkpICsgMSk6CiAgICAgICAgaWYocHJpbWVbaV0pOgogICAgICAgICAgICBmb3IgaiBpbiByYW5nZShpICogaSAsICgxMCAqKiA2ICsgMSApLCBpKToKICAgICAgICAgICAgICAgIHByaW1lW2pdID0gMAoKaWYgX19uYW1lX18gPT0gJ19fbWFpbl9fJzoKICAgIHNhbmcoKQogICAgRiA9IFswXSAqICgxMCAqKiA2ICsgMSApCiAgICBGWzBdID0gMAogICAgRlsxXSA9IDAKICAgIGRlbSA9IDAKICAgIGZvciBpIGluIHJhbmdlKDIgLCAoMTAgKiogNiArIDEgKSk6CiAgICAgICAgaWYocHJpbWVbaV0pOgogICAgICAgICAgICBkZW0gKz0gMQogICAgICAgIEZbaV0gPSBkZW0KICAgIHQgPSBpbnQoaW5wdXQoKSkKICAgIGZvciBpIGluIHJhbmdlKHQpOgogICAgICAgIGwgLCByID0gbWFwKGludCAsIGlucHV0KCkuc3BsaXQoKSkKICAgICAgICBpZihsID09IDApOgogICAgICAgICAgICBwcmludChGW3JdKQogICAgICAgIGVsc2UgOgogICAgICAgICAgICBwcmludChGW3JdIC0gRltsIC0gMV0pCg==

NQozIDE5CjQgNjUKNCA0NAoxIDE3CjEgNwo=

5
3 19
4 65
4 44
1 17
1 7