Prime visits(last case tle)

#1
#2 
import java.util.*;
public class Main {
    public static void main(String args[]) {
       Scanner sc = new Scanner(System.in);

		//use sieve of eratosthenes only once
	
		boolean[] flag = new boolean[1000000];
		for (int i = 0; i <flag.length; i++) {
			if (i == 0 || i == 1) {
				flag[i] = false;
			} else {
				flag[i] = true;
			}
		}

		for (int i = 2; i * i < 1000000; i++) {
			if (flag[i] == true) {
				for (int j = i * 2; j < 1000000; j += i) {
					flag[j] = false;
				}
			}
		}


		int t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			long num1 = sc.nextInt();
			long num2 = sc.nextInt();
				int count = 0;
		for (long j = num1; j <= num2; j++) {
			int c = (int)j;
			if (flag[c] == true) {
				count++;
			}
		}
		System.out.println(count);
		}

	}

	
}