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 
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;
import java.util.InputMismatchException;
public class A
{
    public static void solve()
    {
        int t=sc.nextInt();
        while (t-->0)
        {
           int m = sc.nextInt(), k = sc.nextInt();
           for (int i=0;i<k-3;i++) {
        	   out.print(1+" ");
           }
           int n = m-(k-3);
           if (n%2!=0) {
        	   out.print(n/2+" "+n/2+" "+1);
           }
           else {
        	   if (n/2 %2 !=0) {
        		   out.print((n/2-1)+" "+(n/2-1)+" "+2);
        	   }
        	   else {
        		   out.print((n/2)+" "+(n/4)+" "+(n/4));
        	   }
        	   
           }
           out.println();
        }
    }
    public static void main(String[] args) 
    {
        new Thread(null, null, "Thread", 1 << 27) 
        {
            public void run() 
            {
                try 
                {
                    out = new PrintWriter(new BufferedOutputStream(System.out));
                    sc = new FastReader(System.in);
                    solve();
                    out.close();
                } 
                catch (Exception e) 
                {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }
                .start();
    }
    public static int[] arrprime(int[] prime) {
    	prime[0] = 1;
    	prime[1] = 2;
    	int num = 3;
    	boolean flag = true;
    	for (int i=2;i<1501;) {
    		for (int j=2;j<=Math.sqrt(num);j++) {
    			if (num%j==0) {
    				flag = false;
    				break;
    			}
    			
    		}
    		if (flag) {
    			prime[i] = num;
    			i++;
    		}
    		num++;
    		flag = true;
    	}
    	return prime;
    }
    public static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> 
    {
        public U x;
        public V y;
    
        public Pair(U x, V y) 
        {
            this.x = x;
            this.y = y;
        }
    
        public int hashCode() 
        {
            return (x == null ? 0 : x.hashCode() * 31) + (y == null ? 0 : y.hashCode());
        }
    
        public boolean equals(Object o) 
        {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair<U, V> p = (Pair<U, V>) o;
            return (x == null ? p.x == null : x.equals(p.x)) && (y == null ? p.y == null : y.equals(p.y));
        }
    
        public int compareTo(Pair<U, V> b) {
            int cmpU = x.compareTo(b.x);
            return cmpU != 0 ? cmpU : y.compareTo(b.y);
        }
    
        public String toString() {
            return String.format("(%s, %s)", x.toString(), y.toString());
        }
    
    }
    static final Random random=new Random();
    static int max(int[] arr)
    {
    	int m=Integer.MIN_VALUE;
    	for (int i=0;i<arr.length;i++)
    	{
    		m=Math.max(arr[i], m);
    	}
    	return m;
    }
    static int min(int[] arr)
    {
    	int m=Integer.MAX_VALUE;
    	for (int i=0;i<arr.length;i++)
    	{
    		m=Math.min(arr[i], m);
    	}
    	return m;
    }
    static int gcd(int a,int b)
    {
        if (b==a)
            return a;
        return gcd(b,a%b);
    }
    static void UjjRevSort(int[] a) 
    {
        ArrayList<Integer> arr = new ArrayList(a.length);
        for (int i=0;i<a.length;i++) {
        	arr.add(i, a[i]);
        }
        Collections.sort(arr,Collections.reverseOrder());
        for (int i=0;i<arr.size();i++) {
        	a[i] = arr.get(i);
        }
        
    }
    static void UjjwalSort(int[] a) 
    {
        int n=a.length;//shuffle, then sort 
        for (int i=0; i<n; i++) 
        {
            int ujjwal=random.nextInt(n), temp=a[ujjwal];
            a[ujjwal]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }
    public static PrintWriter out;
    public static FastReader sc;
    public static class FastReader 
    {
        private InputStream stream;
        private byte[] buf = new byte[4096];
        private int curChar, snumChars;
        public FastReader(InputStream stream) 
        {
            this.stream = stream;
        }
        public int read() 
        {
            if (snumChars == -1) 
            {
                throw new InputMismatchException();
            }
            if (curChar >= snumChars) 
            {
                curChar = 0;
                try 
                {
                    snumChars = stream.read(buf);
                } 
                catch (IOException E) 
                {
                    throw new InputMismatchException();
                }
            }
            if (snumChars <= 0) 
            {
                return -1;
            }
            return buf[curChar++];
        }
        public int nextInt() 
        {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = read();
            }
            int number = 0;
            do 
            {
                number *= 10;
                number += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return number * sgn;
        }
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            long sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = read();
            }
            long number = 0;
            do 
            {
                number *= 10L;
                number += (long) (c - '0');
                c = read();
            } while (!isSpaceChar(c));
            return number * sgn;
        }
        public int[] nextIntArray(int n) 
        {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) 
            {
                arr[i] = this.nextInt();
            }
            return arr;
        }
        public long[] nextLongArray(int n) 
        {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) 
            {
                arr[i] = this.nextLong();
            }
            return arr;
        }
        public String next()
        {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        public String nextLine() 
        {
            int c = read();
            while (isSpaceChar(c)) 
            {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do
            {
                res.appendCodePoint(c);
                c = read();	
            } while (!isEndofLine(c));
            return res.toString();
        }
        public boolean isSpaceChar(int c)
        {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        public boolean isEndofLine(int c) 
        {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
}
