D. Math Game
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Aghiad and Aram love math so much. They consider playing video games, sports, and any other activity rather than math a waste of time. But sometimes they get bored from their math problems and want to do something fun without wasting their time. To kill boredom, they came up with a math game that will let them have some fun and waste no time. They write down an array consisting of $$$n$$$ integers. They play in turns, in each turn:

  1. First, Aghiad can choose an element at position $$$i$$$ $$$(1 \le i \lt n)$$$.
  2. Then Aram can choose an element at position $$$j$$$ $$$(i \lt j \le n)$$$.
Now they check if they both scored a point (they are not playing against each other, they are playing together). In this turn, they score a point if and only if the pair they have chosen fulfills this condition:
$$$\LARGE{\frac{a_i^3 + i^3}{a_j^3 + j^3} = \frac{a_i + i}{a_j + j}}$$$ and $$$1 \le i \lt j \le n$$$
If they score a point, they add it to the total and write down on a paper the pair $$$(i,j)$$$ so they can remember it. They cannot choose any pair that was chosen earlier. The game finishes when there are no pairs to choose from. In one day, they wrote an array $$$a$$$ of length $$$n$$$, and they were too busy to play this game, but they were too curious about the total score of this array, so they asked you to tell them the final score.
Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le T \le 10^4 $$$) — the number of test cases in the test.

The first line of each case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of elements in the array.

The second line of each case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_j \le 10^9$$$) — the elements of the array.

It is guaranteed that the sum of the values of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output the score that Aghiad and Aram would achieve if they play the game.

Example
Input
2
3
2 1 1
3
3 3 2
Output
1
3
Note

In the first testcase:

$$$\LARGE{\frac{a_1^3 + 1^3}{a_2^3 + 2^3} = \frac{2^3 + 1^3}{1^3 + 2^3} = 1 = \frac{2 + 1}{1 + 2} = \frac{a_1 + 1}{a_2 + 2}}$$$

In the second testcase, all the pairs satisfy the condition of getting a point.