|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|3 초||1024 MB||8||5||5||83.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.
3 2 2 2 5 2 10
-1 -4 -5
8 2 100 2 50 50 100 2 1000 100 143 2 1000000 80000 90000 1000000 1000000
13 -1 15 63 0 -1909 -31 1
ICPC > Regionals > North America > Pacific Northwest Regional > 2022 ICPC Pacific Northwest Region > Division 2 L번