seuOJ175 - 奇妙数

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：春季, 校赛, 2019

题目描述

有一天某位同学上几代课无聊，就画了一个 $m\times n$ 的矩阵（$m$ 和 $n$ 均为奇数），将 $1$ 到 $mn$ 随机填入其中，发现其中有一些数很奇妙，称它们为奇妙数，它们不仅是所在行（或列）的最大值，还是所在列（或行）的中位数，于是这位同学想知道，在这样的矩阵中这样的数字最多有几个？

输入格式

本题包含多组测试数据，输入的第一行表示测试数据组数 $T(1\leq T\leq 5\times 10^3)$。

对于每组测试数据：第 $1$ 行为两个整数 $m,n(1\leq n,m\leq 5\times 10^3)$且都是奇数。

输出格式

对于每组测试数据，输出 $t$ 行，每行一个整数，表示 $mn$ 的矩阵中奇妙数最多有多少。

样例

样例输入

1
3 3

样例输出

4

样例解释

可构造如下图所示矩阵：

$5,\ 6,\ 7,\ 8$ 为奇妙数，所以一共有 $4$ 个奇妙数。