如今，Dreamgrid 王国正遭受全国性流行病的困扰。幸运的是，Baobao 总统正在与疾病控制中心（CDC）高效合作，他们正竭尽全力控制局势。

Baobao 总统宣布了一项社交距离政策，以防止病毒传播。作为 CDC 的负责人，你需要研究以下问题：

有 $n$ 个人需要被观察，你已经在二维平面上的 $(0, 0)$ 处设置了一个监视器。每个人到监视器的距离都必须在 $r$ 以内。同时，你还需要让他们彼此之间尽可能远离。为了简化问题，你只能将他们分配到整数坐标上。

请最大化 $$\sum_{i=1}^{n-1} \sum_{j=i+1}^{n} d(i, j)^2$$ 其中 $d(i, j)$ 表示第 $i$ 个人和第 $j$ 个人之间的欧几里得距离。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 250$)，表示测试数据的组数。

对于每组测试数据，唯一的一行包含两个整数 $n, r$ ($1 \le n \le 8, 1 \le r \le 30$)。

输出格式

对于每组测试数据，请在一行中输出答案。

样例

样例输入 1

2
4 2
5 10

样例输出 1

64
2496