Distinct Parity Excess

시간 제한3초메모리 제한1024 MB

요약

각 구간 [a,b]에서 서로 다른 소인수의 개수가 짝수인 정수의 개수에서 홀수인 정수의 개수를 뺀 값을 구해 출력한다.

난이도: 보통10점 중 6점
유형: 정수론, 누적 합, 수학
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1
입력
```
3
2 2
2 5
2 10
```
예상 출력
```
-1
-4
-5
```

예제 2

입력

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

예상 출력