2963. 数杯子
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 暑假期间，计算鸭有幸参观了埃及金字塔，他被古埃及人们的智慧深深的折服，回到家后，计算鸭想利用闲置的一次性纸杯仿造属于自己的金字塔。 首先，计算鸭先将一次性纸杯按照$N \timesM$的排列方式摆在桌子上，每一个纸杯紧紧挨在一起。然后第二层每一个杯子都放在第一层相邻的四个杯子的边缘；第三层每一个杯子都放在第二层相邻的四个杯子的边缘.....依次类推。直到杯子无法放在上一个层的其他四个杯子的边缘。  因为工作量很大，计算鸭的先将底层摆放好，当第一层放置好$N\timesM$纸杯后，计算鸭发现如果按照这样摆放的话，极有可能纸杯的数量不够。因此当计算鸭摆放完第一层时，计算鸭会先去算一算这种方式下，至少需要多少纸杯？ 现在给出计算鸭的$t$种摆放方式，请你帮助计算鸭求出每一种摆放方式至少需要纸杯的数量。 ## 输入格式 输入的第一行给出一个整数$t$——表示计算鸭摆 放方式的数量。 接下来$t$行，每行给出两个整数$N,M$——表示第一层摆放的方式。 ## 输出格式 对于，每一个摆放方式，输出该摆放方式的情况下的需要纸杯的数量。 ## 输入 ```in1 3 1 1 2 5 3 3 ``` ## 输出 ```out1 1 14 ``` ## 提示 数据约束与限定 - 子任务一：$30$分：$t,N,M\le100$ - 子任务二：$30$分：$t \le105,N=M,N\le10^6$ - 子任务三：$25$分：$t \le105,N \le106,1\leM\le10^9$ - 子任务四：$15$分：$N \le109,1\leM\le10^9$ 样例解释:当$N=2,M=5$时:堆叠的俯视图如下： 当$M=3,N=3$时，第一层放$9$个纸杯，第二层放$4$个杯子，第三层放$1$个杯子。共使用$9+4+1=14$个杯子