You are given a permutation $a_1,a_2,\ldots,a_n$ of the first $n$ positive integers. A subarray $[l,r]$ is called copium if we can rearrange it so that it becomes a sequence of consecutive integers, or more formally, if $$\max(a_l,a_{l+1},\ldots,a_r)-\min(a_l,a_{l+1},\ldots,a_r)=r-l$$ For each $k$ in the range $[0,n]$, print out the maximum number of copium subarrays of $a$ over all ways of rearranging the last $n-k$ elements of $a$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). It is guaranteed that the given numbers form a permutation of length $n$.

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

Output

For each test case print $n+1$ integers as the answers for each $k$ in the range $[0,n]$.

Note

In the first test case, the answer permutations for each $k$ are $[1,2,3,4,5]$, $[5,4,3,2,1]$, $[5,2,3,4,1]$, $[5,2,1,3,4]$, $[5,2,1,4,3]$, $[5,2,1,4,3]$.

In the second test case, the answer permutations for each $k$ are $[1,2,3,4]$, $[2,1,3,4]$, $[2,1,3,4]$, $[2,1,4,3]$, $[2,1,4,3]$.