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).