Sum of Magic Numbers

You are given Q queries. Each query consists of two integers, l and r, representing a range \([l, r]\). For each query, you need to compute the sum:

\(S = \sum_{i=l}^{r} f(i)\)

where \(f(i)\) is defined as the number of unique prime factors of \(i\). By definition, \(f(1)=0\). For example:

• For \(i = 6\), its prime factors are \(2\) and \(3\), so \(f(6)=2\).
• For \(i = 4\) (which is \(2^2\)), the only prime factor is \(2\), so \(f(4)=1\).

This is a typical problem that can be solved efficiently by precomputing the number of unique prime factors for all numbers up to a certain limit using a sieve method, and then answering each query in constant time using a prefix sum array.

inputFormat

The first line contains a single integer Q (\(1 \le Q\le 10^5\)), denoting the number of queries.

Each of the next Q lines contains two integers l and r (\(1 \le l \le r \le 10^6\)), representing the range for the query.

outputFormat

For each query, output a single line containing the sum \(S = \sum_{i=l}^{r} f(i)\), where \(f(i)\) is the number of unique prime factors of \(i\).

## sample

4
1 1
2 4
10 15
1000 1002

0
3
10
8

</p>