Problem: 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 

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC2 solver = new TaskC2();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC2
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            int T = in.nextInt();
            while (T-- > 0)
            {
                solveOne(in, out);
            }
        }

        private void solveOne(Scanner in, PrintWriter out)
        {
            int N = in.nextInt();
            int K = in.nextInt();
            if (K == 3)
            {
                solveOne3(N, out);
                return;
            }
            int ans[] = new int[K];
            for (int i = 0; i < K; i++)
            {
                ans[i] = N / K;
            }
            int toFill = N - (N / K) * K;
            //out.println(toFill);
            //L.printIntArray(ans, out);
            //out.println();
            //if ((N/K)%2==0){
            int start = 0;
            int end = K - 1;
            while (start < end && toFill > 0)
            {
                ans[start] += ans[end];
                if (toFill == 1) ans[end] = 1;
                else ans[end] = 2;
                toFill -= ans[end];
                start++;
                end--;
            }
            //out.println(toFill);
            L.assertTrue(toFill == 0);
            L.printIntArray(ans, out);
            //}
        }

        private void solveOne3(int N, PrintWriter out)
        {
            if (N == 3)
            {
                print(1, 1, 1, out);
                return;
            }
            if (N == 4)
            {
                print(2, 1, 1, out);
                return;
            }
            if (N % 2 == 0)
            {
                if ((N / 2) % 2 == 0)
                {
                    print(N / 2, N / 4, N / 4, out);
                } else
                {
                    N -= 2;
                    print(N / 2, N / 2, 2, out);
                }
            } else
            {
                print(N / 2, N / 2, 1, out);
            }

        }

        private void print(int a, int b, int c, PrintWriter out)
        {
            out.println(a + " " + b + " " + c);
        }

    }

    static class L
    {
        public static void assertTrue(boolean statement)
        {
            if (!statement) throw new IllegalStateException();
        }

        public static void printIntArray(int[] array, PrintWriter out)
        {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < array.length; i++)
            {
                stringBuilder.append(array[i] + " ");
            }
            out.print(stringBuilder.toString());
        }

    }
}