#215 Choosing Column Prefixes

Statement

Statement language

There are two integer sequences $A$ and $B$ , each of length $N$ . The sequence $A$ satisfies $A_1 \geq A_2 \geq \cdots \geq A_N$ . For $1 \leq i,j \leq N$ , define $C_{i,j}=A_i+B_j$ .

Choose a sequence $P$ of $N$ integers such that $0 \leq P_j \leq N$ and

\sum_{j=1}^{N} P_j=K.

Find the maximum possible value of

\sum_{j=1}^{N}\sum_{i=1}^{P_j} C_{i,j}.

If $P_j=0$ , no element is taken from column $j$ .

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the maximum possible value on one line.

Constraints

$1 \leq T \leq 1\,000$
$1 \leq N \leq 200\,000$
$0 \leq K \leq$

Subtasks

#	Score	Constraints
1	30	$N \leq 50$ , and the sum of $N^2$ over all test cases does not exceed $5\,000$ .
2	70	No additional constraints.

Samples

Input

Output

25
0