Distinct Parity Excess

A property of any positive integer is its prime parity, which is derived from the count of its distinct prime factors. If this count is even, the prime parity is even; if the count is odd, the prime parity is odd.

You are given a sequence of ranges to test. Each range is given as two numbers $a$ and $b$, defining the range from $a$ to $b$ inclusive. You want to compute the excess of even parity integers over odd parity integers over this range. If there are more odd parity integers, the computed difference will be negative.

The first line of the input contains a single integer $n$ $(1\le n\le 100)$, which is the number of ranges to test.

Each of the next $n$ lines contains two integers $a$ and $b$ ($2\le a\le b\le 10^7$), which is a range to test.

Output $n$ lines, one for each range in the input. For each range, output a single integer giving the excess of even parity integers over odd parity integers.