H. Maximizing Pairs
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You may want to use C++ for this problem if you want full credit.

Bronya has $$$n$$$ cards ($$$n$$$ is even), with the $$$i$$$th card having the number $$$a_i$$$ written on it. Given an integer $$$k$$$, she plays the following game:

  1. Initially, Bronya's score is $$$0$$$.
  2. While Bronya has at least two cards in her hand, she picks two cards
  3. She discards the two cards and adds $$$1$$$ to her score if the sum of the numbers on the card is exactly $$$k$$$.

Naturally, Bronya wants to maximize her score for any given $$$k$$$.

Bronya has not yet determined what value of $$$k$$$ she will use. Therefore, your task is to find out what her score will be for each value of $$$k$$$ from $$$1$$$ to $$$2\cdot n$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – the number of independent test cases. The descriptions of test cases follow.

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$). It is guaranteed that $$$n$$$ is even.

The following line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$).

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

Scoring

Partial credits will be given to programs who pass tests with smaller constraints outlined below.

GroupPointsConstraints
150The sum of $$$n$$$ does not exceed $$$5000$$$ over all test cases
250No further constraints.
Output

Output $$$2\cdot n$$$ lines on a new line: the answer for $$$k=1,2,3,\ldots,2\cdot n$$$.

Example
Input
3
4
1 2 3 2
8
1 2 3 4 5 6 7 8
6
1 1 1 1 1 1
Output
0 0 1 2 1 0 0 0 
0 0 1 1 2 2 3 3 4 3 3 2 2 1 1 0 
0 3 0 0 0 0 0 0 0 0 0 0
Note

In the first test case, for $$$k=5$$$, Bronya can earn $$$1$$$ point by doing the following:

  • Pick $$$1$$$ and $$$2$$$ from her hand. Since $$$1+2\neq 5$$$, she does not earn any points.
  • Pick $$$2$$$ and $$$3$$$ from her hand. Since $$$2+3=5$$$, she earns a point.