It is the hard version of the problem. The only difference is that in this version 3 ≤ k ≤ n.

You are given a positive integer n. Find k positive integers a_1, a_2, …, a_k, such that:

  * a_1 + a_2 + … + a_k = n 
  * LCM(a_1, a_2, …, a_k) ≤ n/2 



Here LCM is the [least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple) of numbers a_1, a_2, …, a_k.

We can show that for given constraints the answer always exists.

Input

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

The only line of each test case contains two integers n, k (3 ≤ n ≤ 10^9, 3 ≤ k ≤ n).

It is guaranteed that the sum of k over all test cases does not exceed 10^5.

Output

For each test case print k positive integers a_1, a_2, …, a_k, for which all conditions are satisfied.

Example

Input


2
6 4
9 5


Output


1 2 2 1 
1 3 3 1 1 
"""
#If FastIO not needed, use this and don't forget to strip
#import sys, math
#input = sys.stdin.readline
"""

import os, sys, heapq as h, time
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

#start_time = time.time()

def getInt(): return int(input())
def getStrs(): return input().split()
def getInts(): return list(map(int,input().split()))
def getStr(): return input()
def listStr(): return list(input())
def getMat(n): return [getInts() for _ in range(n)]
def isInt(s): return '0' <= s[0] <= '9'

MOD = 10**9 + 7 

"""
What if N = 4
4
1 1 1 1
5
1 1 1 2
6
1 1 2 2
7
1 2 2 2
8
2 2 2 2
9
4 2 2 1
10
4 2 2 2
11
4 4 2 1
12
4 4 2 2
13
6 3 3 1
14
6 3 3 2
15
6 6 2 1
16
6 6 3 1
17
8 4 4 1
18
8 4 4 2
19
8 8 2 1
20
8 8 2 2
21
10 5 5 1
22
10 5 5 2
23
10 10 2 1
24
10 10 2 2

11, 4
2.75 <= big <= 5.5
So we have 3,4,5 to work with
The biggest number must be >= N/K and <= N/2
The smallest number must be <= N/K

2 1 1 1 1
2 2 1 1 1
2 2 2 1 1
2 2 2 2 1
2 2 2 2 2
4 2 2 2 1
4 2 2 2 2
4 4 2 2 1
4 4 2 2 2
4 4 4 2 1

Biggest number should be math.floor((N-1)/K)*2
We're going to sum up the numbers as follows

X, X, .., X, X/2, ..., X/2, 1, ..., 1

If it's even, we can make it out of 2s and some other number
If it's odd, we can make it out of a 1, 2s and some other number

1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 2
1 1 1 1 1 1 2 2
1 1 1 1 1 2 2 2
...
2 2 2 2 2 2 2 2

1 2 2 2 2 2 2 4

33 7
(33-1)/7 = 4
Highest power of 2 I can use

100001
00241

111111
63
1
111110

As an extension of the three problem, it's
K-3 ones, then solve the original
"""


def solve():
    N, K = getInts()
    ans = [1]*(K-3)
    N -= (K-3)
    if N % 2 == 1:
        ans2 = [1,N//2,N//2]
    elif N % 4 == 0:
        ans2 = [N//4,N//4,N//2]
    else:
        ans2 = [(N-2)//2,(N-2)//2,2]
    print(*(ans+ans2))
    return
    
for _ in range(getInt()):
    #print(solve())
    solve()

#print(time.time()-start_time)