C2. k-LCM (hard version)-Codeforces Round ＃708 (Div. 2)

Problem - 1497C2 - Codeforces

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:

• a1+a2+…+ak=na1+a2+…+ak=n
• LCM(a1,a2,…,ak)≤n2LCM(a1,a2,…,ak)≤n2

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个数表示任意数字需求的答案即可