시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB85583.333%

## 문제

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.

## 예제 입력 1

3
2 2
2 5
2 10


## 예제 출력 1

-1
-4
-5


## 예제 입력 2

8
2 100
2 50
50 100
2 1000
100 143
2 1000000
80000 90000
1000000 1000000


## 예제 출력 2

13
-1
15
63
0
-1909
-31
1


## 출처

• 문제를 만든 사람: Bob Logan