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 CPP):

Solution:
using namespace std; 
#include<bits/stdc++.h>
#define pb push_back
#define mk make_pair
#define vect vector<ll>
#define maap map<ll,ll>  
#define MOD  1000000007
#define mit map::iterator
#define pii pair<ll,ll>
#define rep(i,a,b)	for(ll i=a;i< b;i++)
#define fast  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
typedef  long long   int  ll;
//stringstream convert; 
  //  convert << number; 
  //  string s = convert.str();
 ll fact[500005],invfact[500005]; 
 ll power(ll x, ll y)
{
	ll z = 1;
	while(y > 0)
	{
		if(y % 2 == 1)
			z = (z*x)%MOD;
		x = (x*x)%MOD;
		y /= 2;
	}
	return z;
}
 ll inv(ll x)
{
	return power(x,MOD-2);
}
ll divide(ll x, ll y)
{
	return (x*inv(y))%MOD;
}
ll C(ll n, ll k)
{
	if(k > n) return 0;
	return divide(fact[n], (fact[n - k]*fact[k])%MOD);
}
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
bool isPrime(int n) {
 
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
} 
void init(){
	ll p=MOD;
	fact[0]=1;
	ll i;
	for(i=1;i<500005;i++){
		fact[i]=(i*fact[i-1])%p;
	}
	i--;
	invfact[i]=power(fact[i],p-2);
	for(i--;i>=0;i--){
		invfact[i]=(invfact[i+1]*(i+1))%p;
	}
}
ll s;
ll fun(ll a)
{
	if(a==0)
	return 0;
	return a+fun(a-1);
}
bool comp(pair<pair<ll,ll>,ll >p1,pair<pair<ll,ll>,ll >p2)
{
	if((p1.first.first-p2.first.first)>0&&(p1.first.second-p2.first.second)>0)
	return 1;
	else
	return 0;
}
priority_queue < pair<ll,ll> , vector<pair<ll,ll> >,greater<pair<ll,ll> > > gq;
void update(ll a[],ll* st,ll se ,ll si ,ll i ,ll value, ll index)
{
	if(se==si)
	{
		cout<<i<<" "<<se<<endl;
		a[i]=value;
		st[index]=value;
		return;
	}
	ll mid=se+(si-se)/2;
	if(i<=mid&&i>=se)
	update(a,st,se,mid,i,value,2*index+1);
	else
	update(a,st,mid+1,si,i,value,2*index+2);
	st[index]=st[index*2+1]+st[2*index+2];
}
void makeseg(ll a[],ll se,ll si,ll *st, ll index)
{
	if(se==si)
	{
		st[index]=a[se];
		return;
	}
	ll mid=se+(si-se)/2;
	makeseg(a,se,mid,st,2*index+1);
	makeseg(a,mid+1,si,st,2*index+2);
	st[index]=max(st[index*2+1],st[index*2+2]);
}
ll minq(ll st[],ll si ,ll ei ,ll qs ,ll qe ,ll index)
{
	if(qs<=si&&qe>=ei)
	return st[index];
	if(qs>ei||qe<si)
	return -1;
	ll mid=si+(ei-si)/2;
	return max(minq(st,si,mid,qs,qe,2*index+1),minq(st,mid+1,ei,qs,qe,2*index+2));
} 
void ghost()
{   
  	ll i,j,k,l,m,n,q;
    cin>>q;
    while(q--)
    {
    	cin>>n>>m;
    	l=m-3;
    	ll g=0;
    	while(l--)
    	{g++;
    		cout<<1<<" ";
		}
    	n=n-g;
    	k=n/2;
    	if(n%2==0)
    	{
        if(k%2==0)
        {
        	cout<<k<<" "<<k/2<<" "<<k/2<<endl;
		}
		else
		{
			k--;
			cout<<k<<" "<<k<<" "<<2<<endl;
		}
	}
	else
	{
		cout<<k<<" "<<k<<" "<<1<<endl;
	}
	}
} 
signed main()
{int test=1;
//freopen("input.txt","r",stdin);
//freopen("output.txtlhbvb ","w",stdout);
fast
//cin>>test;
while(test--)
ghost();
return 0;
}