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:
#include<bits/stdc++.h>

#define fo(i,n) for(int i=0;i<n;i++)
#define dsort(arr,n) sort(arr, arr + n, greater<int>())
#define vsortd(a) sort(a.begin(), a.end(), greater<double>())
#define vsort(a) sort(a.begin(), a.end())
#define dbg(x) cout<<#x<<'='<<(x)<<endl;
#define dbg2(x,y) cout<<#x<<'='<<(x)<<endl<<#y<<'='<<(y)<<endl;
#define dbg3(x,y,z) cout<<#x<<'='<<(x)<<endl<<#y<<'='<<(y)<<endl<<#z<<"="<<(z)<<endl;
#define dbg4(x,y,z,w) cout<<#x<<'='<<(x)<<endl<<#y<<'='<<(y)<<endl<<#z<<"="<<(z)<<endl<<#w<<"="<<(w)<<endl;
#define minheap priority_queue <int, vector<int>, greater<int> >
#define maxheap priority_queue <int>
#define test int tc;cin>>tc;while(tc--)
#define ll long long int
#define pb push_back
#define ff first
#define ss second
#define mpr make_pair
#define mkv vector<int>
#define allzero(dp) memset(dp,0,sizeof(dp))
#define endl "\n"
#define print(x) cout<<x<<endl;
#define full(v) v.begin(),v.end()
#define inf INT_MAX

const int mod=1e9+7;
using namespace std;

void fastio()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

bool compare(pair<ll,ll> a,pair<ll,ll> b){
    if(a.first<b.first)return true;
    if(a.first==b.first)return a.second<b.second;
    return false;
}

ll power(ll x, ll y){
    ll res = 1;x=x%mod;
    while(y>0){
        if(y&1)res=(res*x)%mod;
        y=y>>1;x=(x*x)%mod;}
    return res;
}


void solve()
{
    int n,k;cin>>n>>k;
    fo(i,k-3)cout<<1<<" ";
    n=n-(k-3);
    if(n%2==1){
        int a = n/2;
        int b = a;
        int c = 1;
        cout<<a<<" "<<b<<" "<<c<<endl;
    }
    else{
        n/=2;
        if(n%2==0){
            cout<<n<<" "<<n/2<<" "<<n/2<<endl;
        }
        else{
            cout<<n-1<<" "<<n-1<<" "<<2<<endl;
        }
    }
}
int main()
{
    //cout<<fixed<<setprecision(20);

  //  fastio();
     test
    solve();
}