P10925 Happybob's Pancake (UBC001E)

Happybob wants to make a pancake. He decides to make it in a tilted square pan of size $n$ rows and $n$ columns, so the pancake cannot be larger than the tilted square. Because the ingredients are limited, Happybob's pancake must be formed by covering with $m$ rectangles. Happybob wants to know the maximum possible area of the pancake he can make. --- **Formal statement:** Use $m$ rectangles to cover a tilted square of size $n$. What is the maximum number of cells that can be covered? **See the Explanation/Hint for the definitions of the tilted square and covering.**

The first line contains an integer $T$, the number of queries. The next $T$ lines each contain two integers $n, m$, representing one query.

Output $T$ lines, each line containing the answer for one query.

### Sample Explanation The solutions for the three queries are:    (The solutions are not unique.) ### Constraints $1\le T\le 50$, $1\le n\le 2\times 10^9$, $1\le m\le\lceil\dfrac{n}{2}\rceil$. --- ### Formal Definitions **Definition of the tilted square:** More formally, build a Cartesian coordinate system, and define the **center** of a tilted square of size $n$ to be the origin. If $n$ is odd, then this **tilted square** can be described as the combined shape formed by all unit **square cells** (with side length $1$) whose centers are points in $\big\{(x, y) \big | |x| + |y| \le \lfloor \frac{n}{2} \rfloor \text{ and } x, y \in \Z\big\}$. If $n$ is even, then this **tilted square** can be described as the combined shape formed by all unit **square cells** (with side length $1$) whose centers are points in $\big\{(x, y) \big | |x| + |y| \le \frac{n}{2} \text{ and } (x + \frac{1}{2}), (y + \frac{1}{2}) \in \Z\big\}$. A tilted square with $n=5$ (light blue points are cell centers):  A tilted square with $n=6$ (light blue points are cell centers):  **Definition of the covering method:** Define that a rectangle $R$ covers this **tilted square** if and only if $R$ is a rectangle formed by several **cells**. The following is a rectangle that covers a tilted square:  The following are **not** rectangles that cover a tilted square:    Define that a **cell** is covered if and only if among the chosen $m$ rectangles that cover the **tilted square**, at least one completely contains this cell. Translated by ChatGPT 5