题目描述

我们构造一个大小为 $10^9\times10^9$ 的 01 矩阵。其中第 $i$ 行第 $j$ 列是 $1$ 当且仅当 $j|i$。

我们会询问一个子矩阵，左上角为 $(x_1,y_1)$，右下角为 $(x_2,y_2)$。你需要回答子矩阵的每一行中，形成的连续段数量和。

连续段是字面意思，如 0011101 中连续段数量为 $4$。

输入格式

第一行输入一个整数 $T$，表示数据组数。

对于每组数据，唯一的一行输入四个整数 $x_1,y_1,x_2,y_2$。

输出格式

对于每组数据，输出一个整数表示答案。

3
1 1 6 6
7 3 20 8
12345 54321 123456789 987654321

19
38
1927437361

提示

第一组测试数据中，子矩阵的六行分别为 100000，110000，101000，110100，100010，111001，连续段数分别为 $2,2,4,4,4,3$，故答案为 $19$。

数据范围

本题采用捆绑测试。

$1\le T\le 20$，$1\le x_1\le x_2\le 10^9$，$1\le y_1\le y_2\le 10^9$。

记 $V$ 为所有询问中 $x_2,y_2$ 的最大值。

• Subtask 1：$V\le100$。共 $10$ 分。
• Subtask 2：$V\le10^6$。共 $30$ 分。
• Subtask 3：$x_1=x_2$。共 $5$ 分。
• Subtask 4：$y_1=y_2$。共 $15$ 分。
• Subtask 5：$\sum{y_2-y_1}\le 10^6$。共 $10$ 分。
• Subtask 6：无特殊限制。共 $30$ 分。