408126: GYM102993 A Social Distancing

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Social Distancingtime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Nowadays, the Kingdom of Dreamgrid is suffering from a national pandemic. Fortunately, president Baobao is working effectively with the Center for Disease Control (CDC) and they are trying their best to make everything under control.

President Baobao has announced a policy of Social Distancing to prevent the diffusion of the virus. As the chief of CDC, you are required to research on the following problem:

There are $$$n$$$ people who need to be observed and you have already set a monitor in $$$(0,0)$$$ on a 2-dimensional plane. Everyone should stay within the distance of $$$r$$$ to the monitor. You also have to keep them stay away from each other as far as possible. To simplify the problem, you can only allocate them to integers coordinates.

Please maximize $$$$$$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}d(i,j)^2,$$$$$$ where $$$d(i,j)$$$ means the Euclidean distance between the $$$i$$$-th and the $$$j$$$-th person.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ $$$(1 \leq T \leq 250)$$$, indicating the number of test cases.

For each test case, the only line contains two integers $$$n,r$$$ $$$(1 \leq n \leq 8,1 \leq r \leq 30)$$$.

Output

Please output the answer in one line for each test case.

ExampleInput
2
4 2
5 10
Output
64
2496

加入题单

上一题 下一题 算法标签: