E. Hidden Project
time limit per test
4 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

There are $$$N$$$ days. Your normal income is $$$a$$$ baht per day. There are some hidden projects, of which you can conduct as many as you want.

To conduct a project, the rules are as follows:

$$$\scriptsize{\bullet}$$$ Choose integers $$$l$$$, $$$r$$$ such that $$$1 \leq l \leq r \leq N$$$ which represent the days the project starts and finishes, respectively.

$$$\scriptsize{\bullet}$$$ On the $$$i^{th}$$$ day, $$$l \leq i \leq r$$$, you will receive $$$i-l+1$$$ baht.

$$$\scriptsize{\bullet}$$$ You will not receive your normal income on the day between $$$l^{th}$$$ and $$$r^{th}$$$, inclusive.

$$$\scriptsize{\bullet}$$$ There must not be any days more than one project is conducted. For a little clarity, you cannot start a project on the same day you finish another project.

Please find the maximum amount of money that can be earned in $$$N$$$ days.

Input

Each test contains multiple test cases. The first line contains the number of test cases, $$$t$$$ ($$$1 \leq t \leq 10^6$$$). The description of the test cases follows.

The only line of each test case consists of two integers $$$N$$$, $$$a$$$ ($$$1 \leq N \leq 10^4$$$, $$$0 \leq a \leq 10^5$$$) — the number of days and the amount of your normal income, respectively.

Output

For each test case, print a single integer — the maximum amount of money that can be earned in $$$N$$$ days.

Example
Input
3
3 1
3 3
20 21
Output
6
9
420