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>
using namespace std; 
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int long long int
#define ld long double
#define endl "\n"
#define rep(i,a,b) for(int i=a;i<b;i++)
#define reprev(i,a,b) for(int i=b-1;i>=a;i--)
#define all(c) c.begin(),c.end()
#define sz(c) (int)c.size()
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define vin(a,n) vi a(n); rep(k_,0,n) {cin>>a[k_];}
#define vout(a) rep(k_,0,sz(a)) {cout<<a[k_]<<" ";} cout<<endl;
#define pb push_back
#define mp  make_pair
#define mod 1000000007
#define mod2 998244353
#define inf 1e18
#define pi 3.1415926535897932384626
#define tr(container, it) \
for(auto it = container.begin(); it != container.end(); it++)

int power(int x, unsigned int y, int p)  
{  
    int res = 1;     // Initialize result  
  
    x = x % p; // Update x if it is more than or  
                // equal to p 
   
    if (x == 0) return 0; // In case x is divisible by p; 
  
    while (y > 0)  
    {  
        // If y is odd, multiply x with result  
        if (y & 1)  
            res = (res*x) % p;  
  
        // y must be even now  
        y = y>>1; // y = y/2  
        x = (x*x) % p;  
    }  
    return res;  
}

int ceill(int a,int b)
{
    return (a+b-1)/b;
}

signed main()
{
    #ifndef ONLINE_JUDGE
        freopen("./input.txt", "r", stdin);
        freopen("./output.txt", "w", stdout);
    #endif
    IOS
    int t; cin>>t;
    while(t--)
    {
        int n,k; cin>>n>>k; 
        n-=(k-3);
        int m = sqrt(n)+3;
        int spf=n;
        rep(i,2,m)
        {
            if(n%i==0)
            {
                spf=i; break;
            }
        }

        
        if(spf==2)
        {
            if(n%4==0) cout<<n/4<<" "<<n/4<<" "<<n/2<<" ";
            else cout<<n/2-1<<" "<<n/2-1<<" "<<2<<" ";
        }
        else
        {
            cout<<n/2<<" "<<n/2<<" "<<1<<" ";
        }
        rep(i,0,k-3) cout<<1<<" ";
        cout<<endl;
    }
    return 0;
}