JOSWAP - Just One Swap

no tags 

You are given an array of size N. How many distinct arrays can you generate by swapping two numbers for exactly once? The two selected numbers can be equal but their positions in the array must be different.

Input

The first line of the input contains a single integer T, denoting the number of test cases. Every test case starts with an integer N. The next line contains N integers, the numbers of the array.

Output

For each tescase output the answer in a single line.

 

Constraints:

1 <= T <= 5

1 <= Value of a number in the array <= 100000

2 <= N <= 100000


Example

Input:

1
5
2 3 2 3 3

Output:
7

You can generate the following arrays:

2 3 2 3 3

2 2 3 3 3

2 3 3 2 3

2 3 3 3 2

3 2 2 3 3

3 3 2 2 3

3 3 2 3 2



hide comments
sfialok98: 2017-07-30 19:55:02

For Case :
1
2
1 2
What is the expected answer,1 or 2?
Mine with answer 1 getting accepted..

shahzada: 2017-04-30 17:46:56

what should be the answer for -
1
4
1 2 3 4

akshayjhamb2: 2017-04-26 05:00:53

Bertho Coder can u check my solution?

vengatesh15: 2017-04-24 22:10:38

simple combinations Ac in 1 go..

candide: 2017-04-09 12:26:51

Basic combinatorial logic gives the answer. Use long long.

Vipul Srivastava: 2017-04-08 11:54:16

Last edit: 2017-04-08 18:06:44
Vipul Srivastava: 2017-04-07 16:22:00

Are the test cases surely correct?

Reply: Yes, tested by stress testing.

Last edit: 2017-04-07 18:01:49

Added by:Bertho Coder
Date:2017-04-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:National High School Programming Contest 2017