题目描述

给定两个正整数 $n,k$。请你求出最大的整数 $x$ 满足：存在一个整数序列 $a_1,a_2,...,a_n$ 使得

$$\sum_{i=1}^n \sum_{j=i+1}^n |a_i - a_j| = x ，同时 x\le k $$

输入格式

第一行一个正整数 $T$ 表示测试点数量。

接下来 $T$ 行，每行两个正整数 $n,k$， 表示单个测试点内容。

输出格式

$T$ 行，每行一个整数 $x$ 表示满足条件的最大的整数。

4
3 4
4 29
7 108
5 38

4
29
108
38

数据范围

对于 $30\%$ 的数据，$1\le k\le 1000$

对于另外 $30\%$ 的数据，$1\le \sum n\cdot k \le 10^6$

对于 $100\%$ 的数据，$1\le n,k\le 10^5，1\le \sum n,\sum k\le 2\times 10^5$