C2. k-LCM (hard version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
It is the hard version of the problem. The only difference is that in this version 3≤k≤n3≤k≤n.
You are given a positive integer nn. Find kk positive integers a1,a2,…,aka1,a2,…,ak, such that:
Here LCMLCM is the least common multiple of numbers a1,a2,…,aka1,a2,…,ak.
We can show that for given constraints the answer always exists.
Input
The first line contains a single integer tt (1≤t≤104)(1≤t≤104) — the number of test cases.
The only line of each test case contains two integers nn, kk (3≤n≤1093≤n≤109, 3≤k≤n3≤k≤n).
It is guaranteed that the sum of kk over all test cases does not exceed 105105.
Output
For each test case print kk positive integers a1,a2,…,aka1,a2,…,ak, for which all conditions are satisfied.
Example
input
Copy
2 6 4 9 5
output
Copy
1 2 2 1 1 3 3 1 1
=========================================================================
c1的改编，只需要把k-3的1扣掉，把n变成n-(k-3),再利用c1结论，3个数表示任意数字需求的答案即可