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  w(t)                      int t;  cin>>t;  while(t--)
#define  mod1                      1000000007
#define  mod2                      998244353
#define  ll                        long long int
#define  ull                       unsigned long long int
#define  fastIO                    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define  vll                       vector<ll>
#define  vi                        vector<int>
#define  vch                       vector<char>
#define  pll                       pair<ll,ll>
#define  pii                       pair<int,int>
#define  makpii                    make_pair
#define  mpii                      unordered_map<int,int>
#define  sti                       unordered_set<int>
#define  mpci                      unordered_map<char,int>
template<typename T>
T myMax(T x, T y)
{
	return (x > y) ? x : y;
}
struct myComp1          //      sort pairs by second element (MAX)
{
	constexpr bool operator()
	(pair<ll, ll> const& a, pair<ll, ll> const& b)const noexcept
	{
		return a.second < b.second;
	}
};
struct myComp2          //      sort pairs by second element (MIN)
{
	constexpr bool operator()
	(pair<ll, ll> const& a, pair<ll, ll> const& b)const noexcept
	{
		return a.second > b.second;
	}
};
priority_queue<pll, vector<pll>, myComp1> p1; // priority queue with second element in MAX order
priority_queue<pll, vector<pll>, myComp2> p2; // priority queue with second element in MIN order
ll ceili(ll a, ll b)
{
	return a % b == 0 ? (a / b) : (a / b) + 1;
}
int32_t main()
{
	fastIO
#ifndef ONLINE_JUDGE
	freopen("INPUT.txt", "r", stdin);
	freopen("OUTPUT.txt", "w", stdout);
#endif
	w(t)
	{
		ll n,k;
		cin>>n>>k;
		while(k!=3)
		{
			cout<<1<<" ";
			n--;k--;
		}
		if(k==3)
		{
			if (n & 1)
			{
				ll a = n / 2, b = n / 2, c = 1;
				cout << a << " " << b << " " << c << "\n";
			}
			else
			{
				ll A = n / 3, B = n / 3, C = n / 3;
				ll val = n % 3;
				if (val == 0)
				{
					cout << A << " " << B << " " << C << "\n";
				}
				else if ((n / 2) % 2 == 0)
				{
					ll a = n / 2, b = n / 4, c = n / 4;
					cout << a << " " << b << " " << c << "\n";
				}
				else
				{
					ll a = (n / 2) - 1, b = (n / 2) - 1, c = 2;
					cout << a << " " << b << " " << c << "\n";
				}
			}
		}
	}
	return 0;
}
/*
bool prime[1000001];
int primebeh[1000001];
int primesnear[1000001];
void sieve()
{
	int n = 1000000;
	memset(prime, true, sizeof(prime));
	prime[1]=false;
	for (int p = 2; p * p <= n; p++)
	{
		if (prime[p] == true)
		{
			for (int i = p * p; i <= n; i += p)
				prime[i] = false;
		}
	}
	int last = 0;
	for (int i = 2; i <= n; i++)
	{
		if (prime[i])
		{
			primesnear[i] = i;
			last = i;
		}
		else
		{
			primesnear[i] = last;
		}
	}
	for (int i = n; i >= 2; i--)
	{
		if (prime[i])
		{
			primebeh[i] = i;
			last = i;
		}
		else
		{
			primebeh[i] = last;
		}
	}
}
ll power(ll x, ll y, ll p)
{
	ll res = 1; x = x % p; while (y > 0) {if (y & 1) {res = (res * x) % p;} y = y >> 1; x = (x * x) % p;}
	return res;
}
ll modInverse(ll n, int p)
{
	return power(n, p - 2, p);
}
ll nCrModPFermat(ll n, ll r, ll p)
{
	if (n < r)
		return 0;
	if (r == 0)
		return 1;
	ll fac[n + 1];
	fac[0] = 1;
	for (int i = 1; i <= 1000; i++)
		fac[i] = (fac[i - 1] * i) % mod2;
	return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}
}
vector<pair<ll, ll>> pf;
void factorize(ll n) // finds all prime factors of n and their powers in O(logn)
{
	pf.clear();
	int ct = 0;
	while (n % 2 == 0)
	{
		n /= 2;
		ct++;
	}
	if (ct)
		pf.push_back({2, ct});
	for (ll i = 3; i * i <= n; i += 2)
	{
		ct = 0;
		while (n % i == 0)
		{
			n /= i;
			ct++;
		}
		if (ct)
			pf.push_back({i, ct});
	}
	if (n > 2)
		pf.push_back({n, 1});
}
*/