E. Suffix Stack
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ integers. For each index $$$i$$$, perform the following process independently:

Start with an empty stack and read the elements $$$a_i,a_{i+1},\ldots,a_n$$$ from left to right. For each value $$$x$$$:

  • If the stack is not empty and its top value equals $$$x$$$, remove the top value. Do not push $$$x$$$ in this case.
  • Otherwise, push $$$x$$$ onto the stack.

For every $$$i$$$ from $$$1$$$ to $$$n$$$, find the size of the stack after processing all elements from $$$a_i$$$ to $$$a_n$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10000$$$), the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 100000$$$).

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

The sum of $$$n$$$ over all test cases does not exceed $$$100000$$$.

Output

For each test case, print $$$n$$$ integers. The $$$i$$$-th integer must be the size of the stack obtained by starting at index $$$i$$$.

Example
Input
3
5
1 2 2 1 3
4
1 2 1 2
6
1 2 2 3 3 1
Output
1 2 3 2 1
4 3 2 1
0 1 2 1 2 1