任何正整数都有一个属性，称为其素数奇偶性（prime parity），该属性由其不同素因子的个数决定。如果这个个数是偶数，则素数奇偶性为偶；如果这个个数是奇数，则素数奇偶性为奇。

给定一系列需要测试的范围。每个范围由两个数字 $a$ 和 $b$ 给出，定义了从 $a$ 到 $b$（包含 $a$ 和 $b$）的闭区间。你需要计算该范围内偶素数奇偶性整数的数量减去奇素数奇偶性整数的数量所得的差。如果奇素数奇偶性整数更多，则计算出的差为负数。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 100$)，表示需要测试的范围数量。 接下来的 $n$ 行，每行包含两个整数 $a$ 和 $b$ ($2 \le a \le b \le 10^7$)，表示一个需要测试的范围。

输出格式

输出 $n$ 行，每行对应输入中的一个范围。对于每个范围，输出一个整数，表示该范围内偶素数奇偶性整数的数量减去奇素数奇偶性整数的数量所得的差。

样例

样例输入 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