题目描述

4s，512M，pair.in，pair.out

你需要回答 $T$ 次询问。

每次询问，给定 $a,b,c,d$ 。你需要回答满足条件的二元组 $(i,j)$ 个数。

• $a\le i\le b$ 。
• $c\le j\le d$ 。
• $\text{lcm}(i,j)$ 是 MC 数。

其中 MC 数的定义是：如果给定数能表示为 $x^y$，$x,y$ 为正整数，且 $y>1$ , 则这个数是 MC 数，否则这个数不是 MC 数。

输入格式

第一行一个数 $T$ 表示询问组数

接下来 $T$ 行每行四个正整数 $a,b,c,d$ 表示一次询问。

输出格式

输出 $T$ 行。每行一个数。第 $i$ 表示对于第 $i$ 次询问的答案。

样例 #1

样例输入 #1

3
1 2 1 2
1 5 1 5
1 10 1 10

样例输出 #1

1
6
20

提示

对于 $100\%$ 的数据，$1\le a\le b\le 10^6$，$1\le c\le d\le 10^6$，$T\le 10^6$ 。