CF2125C Count Good Numbers

A prime number is a positive integer that has exactly two divisors: $ 1 $ and itself. The first several prime numbers are $ 2, 3, 5, 7, 11, \dots $ . Prime factorization of a positive integer is representing it as a product of prime numbers. For example: - the prime factorization of $ 111 $ is $ 3 \cdot 37 $ ; - the prime factorization of $ 43 $ is $ 43 $ ; - the prime factorization of $ 12 $ is $ 2 \cdot 2 \cdot 3 $ . For every positive integer, its prime factorization is unique (if you don't consider the order of primes in the product). We call a positive integer good if all primes in its factorization consist of at least two digits. For example: - $ 343 = 7 \cdot 7 \cdot 7 $ is not good; - $ 111 = 3 \cdot 37 $ is not good; - $ 1111 = 11 \cdot 101 $ is good; - $ 43 = 43 $ is good. You have to calculate the number of good integers from $ l $ to $ r $ (endpoints included).

The first line contains one integer $ t $ ( $ 1 \le t \le 10^3 $ ) — the number of test cases. Each test case consists of one line containing two integers $ l $ and $ r $ ( $ 2 \le l \le r \le 10^{18} $ ).

For each test case, print one integer — the number of good integers from $ l $ to $ r $ .