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]$$$.

Copium Permutation

Examples