给定一个包含 $n$ 个整数的数组 $a[1..n]$，其中每个整数都在 $1$ 到 $n$ 之间。数组的子段 $a[\ell..r]$ 是指从位置 $\ell$ 到位置 $r$（包含两端）的连续部分。

如果子段 $a[\ell..r]$ 满足以下条件，则称其为 $k$-好（$k$-good）的：

• $r - \ell + 1 \ge 2 \cdot k$，即其长度至少为 $2 \cdot k$；
• $a_\ell = a_{\ell+1} = a_{\ell+2} = \dots = a_{\ell+k-1}$，即其最左侧至少有 $k$ 个元素相等；
• $a_r = a_{r-1} = a_{r-2} = \dots = a_{r-k+1}$，即其最右侧至少有 $k$ 个元素相等；
• $a_\ell = a_r$，即其两端相等。

对于每个从 $1$ 到 $\lfloor \frac{n}{2} \rfloor$ 的 $k$，求出给定数组 $a$ 中 $k$-好子段的数量。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 5 \cdot 10^5$)，表示测试用例的数量。接下来是各测试用例。 每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 5 \cdot 10^5$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。 所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行包含 $\lfloor \frac{n}{2} \rfloor$ 个整数：分别表示对于每个对应的 $k$（从 $1$ 开始），$k$-好子段的数量。

样例

输入 1

4
10
1 2 2 2 2 2 3 2 2 2
6
1 1 1 2 1 1
9
2 2 1 1 1 2 2 1 1
10
3 2 3 2 4 2 10 10 10 10

输出 1

28 11 3 0 0
10 2 0
16 3 0 0
10 1 0 0 0