Problem J: Convenience

Problem J: Convenience

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 549  Solved: 189
[Submit][Status][Web Board]

Description

SUSTech becomes bigger and bigger. The president wants to make the campus more convenient. 

He decided to set n stations in the campus. The stations are built according the DSAA first law:  for i-th station, it is served as the original station for i-th bus line.  For each station, it is served as the destination station for only one bus line.  For each bus line,  the bus in it goes to the destination station directly. Please note that the original and destination station could be the same for some bus lines.

The convenience of the station building plan is measured by the DSAA second law: we use (x, y) to denote we can go from station x and arrive at station y, please note that (1) one passenger could take different bus lines to arrive y from x; (2) (x, y) and (y, x) are different, and (3) (x, x) is allowed.  The convenience of the total plan is defined as the total number of all possible (x, y) pairs among the n stations, the larger the better.

In order to improve the convenience, now we can change the destination of some bus lines according the DSAA third law: we can change at most two destinations of distinct bus lines.

Please find the maximum convenience value we can get by following the DSAA 1st, 2nd and 3rd laws. All stations are labeled from 1 to n.

Input

The first line will be an integer T (1 <= T <= 50). T is the number of test cases.

For each test case, the first line will be an integer n. (1 <= n <= 100000), n is the number of stations.

Then there are n integers. Each integer is the destination of the i-th bus line.

Output

For each test case, print the maximum convenience value.

Sample Input

1
3
2 3 1

Sample Output

9

HINT


We do not need to change any stations.
(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) are all legal. So the
answer is 9.

[Submit][Status]