k bandits robbed a bank. They took away n gold coins. Being a progressive group of robbers they decided to use the following procedure to divide the coins. First the most respected bandit takes 1 coin, then the second respected takes 2 coins, ..., the least respected takes k coins, then again the most respected takes k+1 coins, and so on, until one of the bandits takes the remaining coins. Calculate how much gold each of the bandits gets.

Input

The first line of the input contains number t – the amount of tests. Then t test descriptions follow. Each test consists of two integers n and k - the amount of coins and bandits respectively.

Constraints

1 <= t <= 500
10⁶ <= n <= 10¹⁵
2 <= k <= 100

Output

For each test print the amounts of coins each bandit gets separated by spaces.

Example

Input:
3
1000000 2
1234567 3
123456789 4

Output:
499849 500151
411602 411887 411078
30869901 30858368 30862296 30866224