H. Flip to Zero
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given two integers $$$n$$$ and $$$k$$$. For an integer $$$m$$$ ($$$1 \leq m \leq n$$$), consider a binary string of length $$$n$$$, where the first $$$n-m$$$ characters are $$$0$$$ and the last $$$m$$$ characters are $$$1$$$. You can perform the following operation on it any number of times:

  • Select exactly $$$k$$$ distinct indices of the string. Then flip all bits at the selected indices (i.e., change $$$0$$$ to $$$1$$$, and $$$1$$$ to $$$0$$$).

Let $$$f(m)$$$ be the minimum number of operations required to make all bits in the string $$$0$$$, or $$$-1$$$ if it is impossible.

Your task is to compute $$$f(m)$$$ for all $$$m$$$ from $$$1$$$ to $$$n$$$.

Input

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

The first and only line of each test case contains two integers $$$n$$$ and $$$k$$$ $$$(1 \leq k \leq n \leq 3 \cdot 10^5)$$$.

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

Output

For each test case, output $$$n$$$ integers — the $$$m$$$-th integer represents $$$f(m)$$$.

Example
Input
3
4 1
3 3
7 5
Output
1 2 3 4 
-1 -1 1 
3 2 3 2 1 4 3
Note

In the third test case, we have $$$n=7$$$ and $$$k=5$$$. For $$$m = 3$$$, the string looks like $$$0000111$$$. For this string, we can perform the following operations:

  1. Choose indices $$$\{1, 3, 4, 6, 7\}$$$ in the first operation. The string becomes $$$1011100$$$.
  2. Choose indices $$$\{2, 3, 5, 6, 7\}$$$ in the second operation. The string becomes $$$1101011$$$.
  3. Choose indices $$$\{1, 2, 4, 6, 7\}$$$ in the third operation. The string becomes $$$0000000$$$.

So we can make all bits $$$0$$$ in $$$3$$$ operations. It can be shown that it is impossible to achieve this in less than $$$3$$$ operations. So $$$f(3) = 3$$$.

In the second test case we have $$$n = 3$$$, and $$$k = 3$$$. For $$$m = 1$$$, the string looks like $$$001$$$. For this string, in one operation you can only flip all the bits together. So after one operation, the string becomes $$$110$$$, after two operations, the string becomes $$$001$$$ again. So it is impossible to make all bits $$$0$$$ in this case. So $$$f(1) = -1$$$.