You are given an array $$$a$$$ containing $$$n$$$ integers.

In one operation, you can choose some elements from this array and remove them. However, the elements you choose must meet one of the following conditions:

either all chosen elements are equal;
or there are no two equal chosen elements.

Note that if you choose only $$$1$$$ element to remove, it automatically meets these conditions.

For example, if $$$a = \{1, 2, 1, 1, 3\}$$$, some of the possible elements you can remove in one operation are:

the $$$1$$$-st element;
the $$$1$$$-st and the $$$3$$$-rd element;
the $$$1$$$-st, the $$$3$$$-rd and the $$$4$$$-th element;
the $$$3$$$-rd and the $$$4$$$-th element;
the $$$2$$$-nd, the $$$4$$$-th and the $$$5$$$-th element;
and many others.

However, you cannot choose the $$$2$$$-nd, the $$$3$$$-rd and the $$$4$$$-th element because the $$$2$$$-nd element is not equal to the $$$4$$$-th, but the $$$3$$$-rd element is equal to the $$$4$$$-th.

For each $$$x$$$ from $$$0$$$ to $$$n - 1$$$, you have to calculate the minimum number of operations required to decrease the size of the array to exactly $$$x$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of two lines:

the first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the size of the array;
the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the array itself.

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print $$$n$$$ integers $$$c_0, c_1, \dots, c_{n-1}$$$, where $$$c_i$$$ is the minimum number of operations required to reduce the size of the array to exactly $$$i$$$.

Note

In the first example, the answer can be obtained as follows:

$$$c_{0} = 3$$$: remove $$$a_{8}, a_{9}, a_{10}, a_{11}$$$; then remove $$$a_{1}, a_{2}, a_{3}, a_{4}$$$; then remove $$$a_{5}, a_{6}, a_{7}$$$;
$$$c_{1} = 3$$$: remove $$$a_{8}, a_{9}, a_{10}, a_{11}$$$; then remove $$$a_{1}, a_{2}, a_{3}, a_{4}$$$; then remove $$$a_{5}, a_{6}$$$;
$$$c_{2} = 2$$$: remove $$$a_{7}, a_{8}, a_{9}, a_{10}, a_{11}$$$; then remove $$$a_{1}, a_{2}, a_{3}, a_{4}$$$;
$$$c_{3} = 2$$$: remove $$$a_{7}, a_{8}, a_{9}, a_{10}, a_{11}$$$; then remove $$$a_{1}, a_{2}, a_{3}$$$;
$$$c_{4} = 2$$$: remove $$$a_{7}, a_{8}, a_{9}, a_{10}, a_{11}$$$; then remove $$$a_{1}, a_{2}$$$;
$$$c_{5} = 1$$$: remove $$$a_{1}, a_{7}, a_{8}, a_{9}, a_{10}, a_{11}$$$;
$$$c_{6} = 1$$$: remove $$$a_{7}, a_{8}, a_{9}, a_{10}, a_{11}$$$;
$$$c_{7} = 1$$$: remove $$$a_{1}, a_{2}, a_{3}, a_{4}$$$;
$$$c_{8} = 1$$$: remove $$$a_{1}, a_{2}, a_{3}$$$;
$$$c_{9} = 1$$$: remove $$$a_{1}, a_{2}$$$;
$$$c_{10} = 1$$$: remove $$$a_{7}$$$;

Array Reduction

Examples