有一道题有 $n$ 条提交记录，分别由 $m$ 个人提交，且每个人至少提交了一次。不妨把这 $m$ 个人按 $1\sim m$ 编号，那么这 $n$ 条提交记录可以由一个长为 $n$，值域为 $[1,m]$ 的正整数序列 $a$ 表示。

你打算按顺序浏览一遍这些人的提交记录，但是对于同一个人的，你不想反复「仔细阅读」。同时，你的大脑容量也有限制，只能记录 $k$ 个人的名字。于是，你决定这样做：

• 先给每个人分配一个「优先级」，其中「优先级」是一个 $1\sim m$ 的排列；
• 然后清空大脑，并按顺序浏览提交记录：
  • 如果当前提交的人在大脑里，直接跳过这份提交记录；
  • 否则「仔细阅读」这份提交记录，并把他的名字加入大脑；
  • 任何时刻，只要大脑中超过 $k$ 个名字，就把「优先级」最小的删掉，直到剩下 $\leq k$ 个名字为止。

显然，根据「优先级」的不同，你「仔细阅读」的次数也可能不同。为了省时间，你需要合理安排一个「优先级」，使得你「仔细阅读」的次数最少。

对于 $[1,m]$ 中的每个整数 $k$，回答最少的「仔细阅读」次数。

输入格式

本题有多组数据。第一行一个正整数 $T$（$1\leq T\leq 1.5\cdot 10^5$）表示数据组数。对于每组测试数据：

第一行输入两个正整数 $n,m$（$1\leq m\leq n\leq 5000$）。

第二行一个长为 $n$ 的正整数序列 $a$（$1\leq a_i\leq m$）。保证 $a$ 中 $1\sim m$ 各出现至少一次。

保证 $\sum n\leq 1.5\cdot 10^6,\ \sum n^2\leq 1.5\cdot 10^8$。

输出格式

对于每组数据，输出一行 $m$ 个正整数，其中第 $i$ 个正整数表示当 $k=i$ 时的最小「仔细阅读」次数。

样例

输入

3
5 2
1 2 1 1 2
5 3
2 3 1 3 2
9 3
3 1 2 3 3 1 2 1 3

输出

3 2
4 3 3
6 4 3