← 返回题目列表

Codeforces · 1358/C

C. Celex 更新

中文机器翻译题面 查看原题

隔离期间,Sicromoft 有更多空闲时间在“Celex-2021”中创建新功能。开发者做了一个新函数GAZ-GIZ,它从左上角向右向下无限填充一个无限表,如下:

SUM 函数的开发人员也没有睡觉。由于无聊,他们与 RAND 函数的开发人员合作,因此他们添加了计算从一个单元格到另一个单元格的任意路径上的总和的功能,向下或向右移动。形式上,您可以一步从单元格 $$$(x,y)$$$ 移动到单元格 $$$(x+1, y)$$$ 或 $$$(x, y+1)$$$。

在Dinwows的另一次更新之后,Levian开始学习“Celex-2021”(因为他想成为一名会计师!)。使用 GAZ-GIZ 函数填写表格后,他要求您计算从给定单元格 $$$(x_1, y_1)$$$ 到另一个给定单元格 $$$(x_2, y_2$$$) 的路径上可能存在的不同金额的数量,前提是您只能向下或向右移动一个单元格。

正式地,考虑从单元格 $$$(x_1, y_1)$$$ 到单元格 $$$(x_2, y_2)$$$ 的所有路径,使得路径中的每个下一个单元格位于前一个单元格的下方或右侧。计算所有此类路径的不同元素和的数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 57179$$$) — 测试用例的数量。

以下 $$$t$$$ 行包含四个自然数 $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \le x_1 \le x_2 \le 10^9$$$, $$$1 \le y_1 \le y_2 \le 10^9$$$) — 起始和结束单元格的坐标。

输出

对于每个测试用例,在单独的行中打印从起始单元格到结束单元格之间可能的不同总和的数量。

示例

输入 #1

4
1 1 2 2
1 2 2 4
179 1 179 100000
5 7 5 7

输出 #1

2
3
1
1

注意

在第一个测试用例中,有两个可能的总和:$$$1+2+5=8$$$ 和 $$$1+3+5=9$$$。