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.util.*;
import java.io.*;
import java.math.BigInteger;
public class Main {
	//  Solution 
    public static void main(String [] args) throws IOException {
    	//Dir by MohammedElkady
    	int tt=in.nextInt();
    	while(tt-->0) {
    	int n = in.nextInt(),m = in.nextInt();
        while(m>3) {
        	n--;
        	out.append("1 ");
        	m--;}
        
        if(n%2==1) {out.append(1+" ");n--;}
        else if((n/2)%2==0) {out.append(n/2+" ");n/=2;}
        else {out.append(2+" ");n-=2;}
    	out.append(n/2+" "+n/2+"");
        	out.append("\n");
    }
    	out.close();
    }
    static long mod=1000000007L;
    static long gcd(long a,long b) {
    	if(a==0)
    		return b;
    	return gcd(b%a,a);
    }
    static long dp[][][];
    static long vor(int i, int u,int t) {
    	if(t>1)
    		return -1;
    	if(dp[i][u][t]!=0) 
    		return dp[i][u][t];
    	long a=vor(i-1,u-1,t),b=vor(i-1,u-1,t);
    	
    	return 0;
    }
    static Reader in=new Reader();
    public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static class Reader 
    { 
        private InputStream mIs;private byte[] buf = new byte[1024];private int curChar,numChars;public Reader() { this(System.in); }public Reader(InputStream is) { mIs = is;} 
        public int read() {if (numChars == -1) throw new InputMismatchException();if (curChar >= numChars) {curChar = 0;try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}if (numChars <= 0) return -1; }return buf[curChar++];} 
        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 String s(){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 long l(){int c = read();while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }long res = 0; do{ if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read();}while(!isSpaceChar(c));return res * sgn;} 
        public int nextInt(){int c = read() ;while (isSpaceChar(c)) c = read();int sgn = 1;if (c == '-') { sgn = -1 ; c = read() ; }int res = 0;do{if (c < '0' || c > '9') throw new InputMismatchException();res *= 10 ; res += c - '0' ; c = read() ;}while(!isSpaceChar(c));return res * sgn;} 
        public double d() throws IOException {return Double.parseDouble(s()) ;}
        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; } 
        public int[] arr(int n){int[] ret = new int[n];for (int i = 0; i < n; i++) {ret[i] = nextInt();}return ret;}
    }
}
class node implements Comparable<node> {
int val,pos;
node(int val,int pos){
	this.pos=pos;this.val=val;
}
@Override
public int compareTo(node o) {
	
	return val-o.val;
}
 
 
}
class xtree{
	public xtree(int n,int a[]) {
		this.a=a;
		seg=new int[n*4];
		//lazy=new int[n*4];
		build(1,0,n-1);
	}
	int seg[], a[],lazy[];
	    void check(int p,int s,int e) {
	        if(lazy[p]!=0) {
	            seg[p] += lazy[p];
	            if(s!=e) {
	                lazy[2*p] += lazy[p];
	                lazy[2*p+1] += lazy[p];
	            }
	            lazy[p] = 0;
	        }
	    }
	    
	     void build(int p,int s,int e) {
	        //check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = a[s];
	            return;
	        }
	        
	        build(2*p,s,(s+e)/2);
	        build(2*p+1,(s+e)/2+1,e);
	        
	        seg[p] = seg[2*p]+ seg[2*p+1];
	    }
	    
	   void update(int p,int s,int e,int i,int v) {
	       // check(p,s,e);
	        
	        if(s==e) {
	            seg[p] = v;
	            return;
	        }
	        
	        if(i<=(s+e)/2) update(2*p,s,(s+e)/2,i,v);
	        else update(2*p+1,(s+e)/2+1,e,i,v);
	        
	        seg[p] = seg[2*p]+seg[2*p+1];
	    }
	    
	     void update(int p,int s,int e,int a,int b,int v) {
	        //check(p,s,e);
	        
	        if(s>=a && e<=b) {
	            seg[p] += v;
	            
	            if(s!=e) {
	                lazy[2*p] += v;
	                lazy[2*p+1] += v;
	            }
	            
	            return;
	        }
	        
	        if(s>b || e<a)
	            return;
	        
	        update(2*p,s,(s+e)/2,a,b,v);
	        update(2*p+1,(s+e)/2+1,e,a,b,v);
	        
	        seg[p] = seg[2*p]+seg[2*p+1];
	    }
    
 
    
    int get(int p,int s,int e,int a,int b) {
        if(s>=a && e<=b)
            return seg[p];
        
        if(s>b || e<a)
            return 0; 
        
        return get(2*p,s,(s+e)/2,a,b)+ get(2*p+1,(s+e)/2+1,e,a,b);
    }
}
 
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;
        }
}
 
class Sorting{
 
 public static int[] bucketSort(int[] array, int bucketCount) {
 
 if (bucketCount <= 0) throw new IllegalArgumentException("Invalid bucket count");
 
 if (array.length <= 1) return array; //trivially sorted
 
 
 
 long high = array[0];
 
 long low = array[0];
 
 for (int i = 1; i < array.length; i++) { //find the range of input elements
 
 if (array[i] > high) high = array[i];
 
 if (array[i] < low) low = array[i];
 
 }
 
 double interval = ((double)(high - low + 1))/bucketCount; //range of one bucket
 
 
 ArrayList<Integer> buckets[] = new ArrayList[bucketCount];
 
 for (int i = 0; i < bucketCount; i++) { //initialize buckets
 
 buckets[i] = new ArrayList();
 
 }
 
 
 
 for (int i = 0; i < array.length; i++) { //partition the input array
 
 buckets[(int)((array[i] - low)/interval)].add(array[i]);
 
 }
 
 
 int pointer = 0;
 
 for (int i = 0; i < buckets.length; i++) {
 
 Collections.sort(buckets[i]); //mergeSort
 
 for (int j = 0; j < buckets[i].size(); j++) { //merge the buckets
 
 array[pointer] = buckets[i].get(j);
 
 pointer++;
 
 }
 
}
 
return array;
 
}
}
 class LongestCommonSubsequence 
{ 
  
  /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
	 int lcs( char[] X, char[] Y, int m, int n ,int K) 
	  { 
		 int L[][] = new int[m+1][n+1]; 
		 int ans[][]=new int[m+1][n+1];
		 int min[][] = new int[m+1][n+1]; 
		 for(int i=0;i<=n;i++) 
			 for(int j=0;j<=m;j++) 
				 min[j][i]='z'+1;
	    /* Following steps build L[m+1][n+1] in bottom up fashion. Note 
	         that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
	    for (int i=0; i<=m; i++) 
	    { 
	      for (int j=0; j<=n; j++)
	      { 
	        if (i == 0 || j == 0) 
	            L[i][j] = 0; 
	        else if (X[i-1] == Y[j-1]) { 
	            L[i][j] = L[i-1][j-1] + 1; 
	            ans[i][j]=ans[i-1][j-1]+X[i-1];
	         
	        }
	        else {
	            L[i][j] = max(L[i-1][j], L[i][j-1]); }
	      } 
	    } 
	  return L[m][n]; 
	  } 
	  
	  /* Utility function to get max of 2 integers */
	  int max(int a, int b) 
	  { 
	    return (a > b)? a : b; 
	  } 
 
     // Returns length of LCS for X[0..m-1], Y[0..n-1] 
     static String lcs(String X, String Y, int m, int n) 
     { 
         int[][] L = new int[m+1][n+1]; 
    
         // Following steps build L[m+1][n+1] in bottom up fashion. Note 
         // that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]  
         for (int i=0; i<=m; i++) 
         { 
             for (int j=0; j<=n; j++) 
             { 
                 if (i == 0 || j == 0) 
                     L[i][j] = 0; 
                 else if (X.charAt(i-1) == Y.charAt(j-1)) 
                     L[i][j] = L[i-1][j-1] + 1; 
                 else
                     L[i][j] = Math.max(L[i-1][j], L[i][j-1]); 
             } 
         } 
    
         // Following code is used to print LCS 
         int index = L[m][n]; 
         int temp = index; 
    
         // Create a character array to store the lcs string 
         char[] lcs = new char[index+1]; 
         lcs[index] = '\u0000'; // Set the terminating character 
    
         // Start from the right-most-bottom-most corner and 
         // one by one store characters in lcs[] 
         int i = m; 
         int j = n; 
         while (i > 0 && j > 0) 
         { 
             // If current character in X[] and Y are same, then 
             // current character is part of LCS 
             if (X.charAt(i-1) == Y.charAt(j-1)) 
             { 
                 // Put current character in result 
                 lcs[index-1] = X.charAt(i-1);  
                   
                 // reduce values of i, j and index 
                 i--;  
                 j--;  
                 index--;      
             } 
    
             // If not same, then find the larger of two and 
             // go in the direction of larger value 
             else if (L[i-1][j] > L[i][j-1]) 
                 i--; 
             else
                 j--; 
         } 
    
         // Print the lcs 
         StringBuilder Sd=new StringBuilder();
         for(int k=0;k<=temp;k++) 
             Sd.append(lcs[k]); 
      return Sd.toString();   
     }
 }