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;
namespace debug {
    #ifdef local
    #define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
    #else
    #define dbg(...)
    #endif
    void err() {
        cout << endl;
    }
    template<template<typename...> class T, typename t, typename... Args>
    void err(T<t> a, Args... args) {
        for (auto x: a)
            cout << x << ' ';
        err(args...);
    }
    template<typename T, typename... Args>
    void err(T a, Args... args) {
        cout << a << ' ';
        err(args...);
    }
}
using namespace debug;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define setbits(x)      __builtin_popcountll(x)
#define trailzero(x)    __builtin_ctz(x)
#define leadzero(x)     __builtin_clz(x)
#define ffs(a)          __builtin_ffs(a) //first set bit
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mod             1000000007
#define int             long long int
#define ll              long long
#define ld              long double
#define ff              first
#define ss              second
#define pb              push_back
#define eb              emplace_back
#define popb            pop_back
#define endl            '\n'
#define all(v)          v.begin(), v.end()
#define sz(x)           ((int)((x).size()))
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef pair<int, pii> pip;
typedef pair<pii, int> ppi;
typedef pair<string, string> pss; 
typedef vector<int> vi; 
typedef vector<vi> vvi; 
typedef vector<pii> vii;
typedef vector<pll> vll; 
typedef vector<ll> vl; 
typedef vector<vl> vvl;
typedef vector<string> vs;

ll power(ll a, ll b) {
    if(b<0) return 1;
    ll res=1;
    while(b) {
        if(b&1) 
            res = (res*a);//%mod;
        a = (a*a);//%mod;
        b >>= 1;
    }
    return res;
}
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
bool ispoweroftwo(ll x){ return (x&&!(x&(x-1)));}
ll GCD(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
ll LCM(ll a, ll b) {return a / GCD(a, b) * b;}
const int inf = 1e9;
const ll INF = 1e18;
const ld pi = 3.141592653589793238;
int dx[] = {-1, 0, 1, 0}; 
int dy[] = {0, 1, 0, -1};
char MV[] = {'U', 'R', 'D', 'L'};
//integer to char always remember (char+'0')
//----------------------------------------------------------------------------------------

void solve() {
    int n, k; cin >> n >> k;

    for (int i = 1; i <= (k-3); ++i) cout << "1 ";
    if(n == 0) return void(cout << endl);
    
    n -= (k-3);
    
    if(n%2) {
        cout << "1 " << n/2 << ' ' << n/2 << endl; 
    }
    else {
        if((n/2)%2)
            cout << "2 " << n/2-1 << ' ' << n/2-1 << endl;
        else
            cout << n/4 << ' ' << n/4 << ' ' << n/2 << endl;
    }
}

int32_t main() {
    FIO;
    int t; cin >> t; while(t--)
    solve();
    return 0;
}