Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

For an undirected graph $G$ with $n$ nodes and $m$ edges, we can define the distance between $(i,j)$ ($\text{dist}(i,j)$) as the length of the shortest path between $i$ and $j$. The length of a path is equal to the number of the edges on it. Specially, if there are no path between $i$ and $j$, we make $\text{dist}(i,j)$ equal to $n$.

Then, we can define the weight of the graph $G$ ($w_G$) as $\sum_{i=1}^n \sum_{j=1}^n \text{dist}(i,j)$.

Now, Yuta has $n$ nodes, and he wants to choose no more than $m$ pairs of nodes $(i,j)(i \neq j)$ and then link edges between each pair. In this way, he can get an undirected graph $G$ with $n$ nodes and no more than $m$ edges.

Yuta wants to know the minimal value of $w_G$.

It is too difficult for Rikka. Can you help her?  

In the sample, Yuta can choose $(1,2),(1,4),(2,4),(2,3),(3,4)$.

Input

The first line contains a number $t(1 \leq t \leq 10)$, the number of the testcases.

For each testcase, the first line contains two numbers $n,m(1 \leq n \leq 10^6,1 \leq m \leq 10^{12})$.

Output

For each testcase, print a single line with a single number -- the answer.

1
4 5

14