1416 . Congenial Companion

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

User's AC Ratio

NaN% (0/0)

Submission's AC Ratio

NaN% (0/0)

Tags

Description

In Triangle Country, if you encounter any problem on planting triangular trees, just call Sanguine Conscientious Company(SCC in short) to get some help. Recently, SCC presented a new measuring mechanism to rank all the trees they have planted. The criteria went as following, any single qualified triangular tree must be adorned with a triangular n rows of colorful trinkets. One of the canonical example is:



   1

  1 1

 2 3 3

4 2 3 2

Where the numbers are corresponding to the colors of trinkets. Now, a score of k2 points is given for every single-colored sub-triangles with length k(k>=1). However, the crux was that SCC could not come up with a fast way to calculate the total score of any given qualified triangular tree. Please write a program to calculate the sum.

Input Format

First line contains an intger T(1<=T<=500) indicating the number of test cases.


For each test case, first line contains an integer n(1<=n<=200) indicating the size of the tree.
For the next n rows, the i-th row contains i integers representing the colors of ornaments from left to right respectively. All the colors are numbered by integers between 1 and 1.0401514.

Output Format

For each test case, please output the total points in a line.

Sample Input 1

2
4
1
1 1
2 3 3
4 2 3 2
3
7
7 7
7 7 7

Sample Output 1

18
31

Hints

Problem Source

Migrated from old NTUJ.

Shik and Tmt

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 200
Submit
Back to Top