This is the hard version of the problem. The difference between the versions is that in this version, you need to solve the problem for different values of $k$. You can hack only if you solved all versions of this problem.

Alp loves carrots. Since he hasn't eaten lunch yet, he wants to buy a carrot salad to eat outside. However, he has a weird obsession: all the carrots must be the exact same length; otherwise, the salad doesn't look aesthetically pleasing to him. Since he is in the middle of the street and doesn't have a knife, he can't cut the carrots himself. You need to divide all the carrots using your machine and sell them to Alp.

You are given $n$ delicious carrots with sizes $a_1, a_2, \ldots, a_n$. You are also given a cutting machine, which works as follows.

• For each operation, you choose a set of carrots (you can choose chopped carrots again) and a positive integer $x$ (not necessarily the same for each operation).
• After that, consider every chosen carrot, let its length be $l$. If $l \le x$, this carrot is unaffected; otherwise, it is divided into two carrots of sizes $x$ and $l-x$.

We'll sell some of the final carrots to an interesting guy who wants them all to be the same length.

We are asking you to determine the maximum number of carrots we can sell after using this machine exactly $k$ times. Solve the problem for each $k = 1, 2, \ldots, m$ independently.

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 $n$ and $m$ ($1 \le n,m \le 2 \cdot 10^5$), denoting the number of carrots and the maximum possible length of a carrot.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le m$), denoting the initial carrot sizes.

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

Output

For each test case, output $m$ integers — the answer for each $k=1, 2, \ldots, m$.

Note

In the first test case, the given carrots are $[1, 2, 3, 4, 4]$.

For $k=1$, it is best to choose $x=2$ with the set $[2, 3, 4, 4]$. After the operation, we'll get $[1, 2, 2, 1, 2, 2, 2, 2]$. We can sell $6$ carrots of length $2$.

For $k=2$, it is best to choose $x=2$ with the set $[2, 3, 4, 4]$. After the operation, we'll get $[1, 2, 2, 1, 2, 2, 2, 2]$. For the second operation, it is best to choose $x=1$ with the set of all of the carrots. Resulting in $14$ carrots, all of the same length. We can sell $14$ carrots of length $1$.