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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    // Hashmap
    // m.put(arr[i],m.get(arr[i])!=null?m.get(arr[i])+1:1);
    public static void main(String[] args) {
        FastReader in = new FastReader();
        int t=in.nextInt();
        while(t-->0)
        {
            int n=in.nextInt();
            int k=in.nextInt();
            int ex1=k-3;
            fun(n-ex1);
            for(int i=0;i<k-3;i++)
            {
                System.out.print(1+" ");
            }
            System.out.println();

        }
    }
    public static void fun(int n)
    {
        if(isodd(n))
        {
            System.out.print(n/2+" "+n/2+" "+1+" ");
        }else
        {
            int ans=n/2;
            if(ans%2==0)
            {
                System.out.print(n/2+" "+n/4+" "+n/4+" ");
            }
            else
            {
                int fans=(n/2)-1;
                System.out.print(fans+" "+fans+" "+2+" ");
            }
        }
    }
    static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    static int lcm(int a, int b)
    {
        return (a / gcd(a,b)) * b;
    }
    static class Pair
    {
        // Return a map entry (key-value pair) from the specified values
        public static <T, U> Map.Entry<T, U> of(T first, U second)
        {
            return new AbstractMap.SimpleEntry<>(first, second);
        }
    }
    static long log(long a,long b)
    {
        long ret=0;
        while(a>0)
        {
            a/=b;
            ret++;
        }
        return ret;
    }
    static long log2(int a)
    {
        return (int) (Math.log(a)/Math.log(2));
    }
    static boolean isodd(int n)
    {
        if((n&1)==1)
            return true;
        else
            return false;
    }
    static int longestPrefixSuffix(String s)
    {
        int n = s.length();

        // If n is less than 2
        if(n < 2) {
            return 0;
        }

        int len = 0;
        int i = (n + 1)/2;

        // Iterate i till n
        while(i < n)
        {

            // If s[i] is equal to
            // s[len]
            if(s.charAt(i) == s.charAt(len))
            {
                ++len;
                ++i;
            }
            else
            {
                i = i - len + 1;
                len = 0;
            }
        }

        // Return len
        return len;

    }
    static boolean isPowerOfTwo(int x)
    {
        /* First x in the below expression is
        for the case when x is 0 */
        return x != 0 && ((x & (x - 1)) == 0);
    }
    public static int upperbound(int arr[],int key)
    {
        int low=0;
        int high=arr.length-1;
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(arr[mid]>key)
            {
                high=mid-1;
            }else if(arr[mid]==key)
            {
                low=mid+1;
            }
            else
            {
                low=mid+1;
            }
        }
        return low;
    }
    public static int lowerbound(int arr[],int key)
    {
        int low=0;
        int high=arr.length-1;
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(arr[mid]>key)
            {
                high=mid-1;
            }else if(arr[mid]==key)
            {
                high=mid-1;
            }
            else
            {
                low=mid+1;
            }
        }
        return low;
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader()
        {
            br = new BufferedReader(
                    new InputStreamReader(System.in));
        }

        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() { return Integer.parseInt(next()); }

        long nextLong() { return Long.parseLong(next()); }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}