Rooks - Repovive Premier Round 1 | Repovive

2A. Rooks

500 pts2s256 MB

You are given an $n \times n$ chessboard. You must place exactly $m$ rooks on distinct cells.

A cell is called threatened if there exists at least one rook in the same row or in the same column (the cell may also contain a rook).

For each test case, find the minimum possible number of threatened cells.

Constraints

$1 \le t \le 100$
$1 \le n \le 10^9$
$1 \le m \le n^2$

Input

t \\[0.5em] \left. \begin{array}{l} n \quad m \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

Samples

Input

Explanation

Case 1

Put the rooks at $(1,1)$ and $(1,2)$ .
Then all cells in row $1$ are threatened, and all cells in columns $1$ and $2$ are threatened.
So the only safe cells are $(2,3)$ and $(3,3)$ (all other $7$ cells are threatened).

Case 2

Put the rooks at $(1,1)$ , $(1,2)$ , and $(2,1)$ .
Then all cells in rows $1$ and $2$ are threatened, and all cells in columns $1$ and $2$ are threatened.
So the only safe cell is $(3,3)$ (the other $8$ cells are threatened).

Output

You are given an $n \times n$ chessboard. You must place exactly $m$ rooks on distinct cells.

A cell is called threatened if there exists at least one rook in the same row or in the same column (the cell may also contain a rook).

For each test case, find the minimum possible number of threatened cells.

Constraints

$1 \le t \le 100$
$1 \le n \le 10^9$
$1 \le m \le n^2$

t \\[0.5em] \left. \begin{array}{l} n \quad m \end{array} \right\} \times t

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

2A. Rooks

Input

Output

Samples

2A. Rooks

Constraints

Input

Output

Samples

Constraints