3982: 【NOIP2022赛前训练】二元组(pair)

pair.in/out/cpp

## 题目描述

你需要回答 $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
```