Processing math: 100%

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 3kn.

You are given a positive integer n. Find k positive integers a1,a2,,ak, such that:

  • a1+a2++ak=n
  • LCM(a1,a2,,ak)n2

Here LCM is the least common multiple of numbers a1,a2,,ak.

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

Input

The first line contains a single integer t (1t104)  — the number of test cases.

The only line of each test case contains two integers n, k (3n109, 3kn).

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

Output

For each test case print k positive integers a1,a2,,ak, for which all conditions are satisfied.

Example
Input
2
6 4
9 5
Output
1 2 2 1 
1 3 3 1 1