15837번 - Sum of Subrectangle Areas 다국어

문제

The following code snippet calculates the sum of the areas of all the sub rectangular grid in a rectangular grid from (0,0) to (N,N). Find an efficient way to compute that.

sum = 0
for r1 = 0 to N-1
 for c1 = 0 to N-1
 for r2 = r1+1 to N
 for c2 = r2+1 to N
 sum = sum + (r2-r1)*(c2-c1)
print(sum)

입력

Input starts with T the number of test cases. Each test case consists of a single integer N.

출력

For each test output the sum (as computed above). Please note that even though N will fit into 64 bit integer, the sum may not be.

제한

힌트