public static void main(String[] args){
	    Scanner in = new Scanner(System.in);
		luckeyNumbers_solution obj = new luckeyNumbers_solution();
		
		obj.gen_primes();
	    obj.gen_table();
	    
	    for(int i=0;i<=18;i++)
	        for(int j=0;j<=163;j++)
	            {
	                for(int k=0;k<=1458;k++)
	                        if(obj.dyn_table[i][j][k]!=0)
	                            {
	                                obj.start[i][j] = k;
	                                break;                               
	                            }

	                for(int k=1460;k>=0;k--)
	                        if(obj.dyn_table[i][j][k]!=0)
	                            {
	                                obj.end[i][j]=k;
	                                break;                               
	                            }
	            }
	//upto here..........3
	    int cases = 0;
	    cases = in.nextInt();
	    for (int i = 0; i < cases; ++i) {
	        long a, b;

	        a = in.nextLong();
	        b = in.nextLong();
	//changed here......4
	        if(b == (long)1000000000000000000l)
	            b--;
	//upto here.........4
	        System.out.println(obj.count_lucky(b) - obj.count_lucky(a-1));
	    }
	    return ;
	}