import java.util.Scanner;

public class distinctparity_da {

    private void work() {
        int[] s = new int[10000001];
        for (int i = 2; i < s.length; i++) {
            if (s[i] == 0) {
                for (int j = i; j < s.length; j += i) {
                    s[j]++;
                }
            }
        }

        for (int i = 2; i < s.length; i++) {
            if ((s[i] & 1) == 0) {
                s[i] = s[i - 1] + 1;
            } else {
                s[i] = s[i - 1] - 1;
            }
        }

        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        while (tc-- > 0) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            System.out.println(s[b] - s[a - 1]);
        }

        sc.close();
    }

    public static void main(String[] args) {
        new distinctparity_da().work();
    }
}
