Alice and Bob
Description
You are watching Alice and Bob playing a game.
The game is played on an array of length $n$. Alice and Bob take turns in action, Alice goes first.
In each turn, the current player can select two different numbers $a_i$ and $a_j$ in the array, and then change their values. Assume after changes the values of them are $a_i'$ and $a_j'$ , then an operation is legal if and only if $a_i+a_j=a_i'+a_j'$ and $|a_i'-a_j'|< |a_i-a_j| $. Those who cannot perform legal operations lose.
After playing a few games, You decided to help Alice, because Alice, who was always overloaded when faced with a bunch of numbers, always unable to think in front of the genius Bob.
Before the start of each game, You will help Alice remove several numbers (could be $0$) to reduce the burden on her brain, and you always leave exactly three numbers. And in order to give Alice a greater chance of winning, You will always leave Alice with a winning state, that is, there must be some kind of operating strategy that makes Alice must win no matter how Bob acts.
Now the question is how many ways there are to remove the numbers.
Two ways for removing numbers are considered different if and only if there exists an integer $i\ (1\le i\le n)$ such that $a_i$ is not removed in one way and is removed in the other way.
The first line contains a single integer $T$ , representing the number of test cases.
Then follow the descriptions of each test case.
The first line contains an integer $n(3\le n\le 5\times 10^5)$ , which represents the number of numbers at the beginning.
The second line contains $n$ integers $a_1,a_2,a_3,\dots,a_n(0\le a_i\le 10^{18})$, representing the original $n$ numbers.
It's guaranteed that $\sum n\le 3\times 10^6$ .
For each test case, output one integer in one line, indicating the number of different ways to remove numbers that satisfy the condition.
Input
The first line contains a single integer $T$ , representing the number of test cases.
Then follow the descriptions of each test case.
The first line contains an integer $n(3\le n\le 5\times 10^5)$ , which represents the number of numbers at the beginning.
The second line contains $n$ integers $a_1,a_2,a_3,\dots,a_n(0\le a_i\le 10^{18})$, representing the original $n$ numbers.
It's guaranteed that $\sum n\le 3\times 10^6$ .
Output
For each test case, output one integer in one line, indicating the number of different ways to remove numbers that satisfy the condition.
3
4
2 0 2 3
3
2 2 3
3
0 2 3
3
0
1
Note
In the first test case, only removing $a_2$ leaves a loser state.