Problem Description

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.

Input Format

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 Format

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

3
5 1
6 2
8 2

9
20
32

Hint

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