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:
/*     JAI SHREE RAM

	MANDIR WAHI BANEGA
	  */



#include <bits/stdc++.h>
using namespace std;

// Big two primes
#define X 1001100011100001111ll
#define mod 1000000007
#define int long long
#define ll long long
#define all(a) a.begin(),a.end()
#define sortall(a) sort(all(a))
#define fo(i, n) for (int i = 0; i < n; i++)
#define fo1(i, n) for (int i = 1; i <= n; i++)
#define loop(i,a,b) for (int i = a; i < b; i++)
#define nloop(i,a,b) for (int i = a ; i>=b;i--)
#define tc(t) int t; cin >> t; while (t--)
#define arrip(a,n)  int a[n]; fo(i, n) cin >> a[i];
#define arrop(a,n)  fo(i,n) cout<<a[i]<<" ";
#define pb push_back
#define mp make_pair
#define itr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626

#define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define rr return 0
#define prec(n) fixed<<setprecision(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define inf (int)(1e18)
#define ini(a, i) memset(a, i, sizeof(a))
#define vi vector<int>
#define fi first
#define se second
#define endl "\n"
#define pi pair<int, int>
#define vpi vector<pi>
#define sz(s) s.size()
#define bits(n) __builtin_popcount(n)
//const int MAXN = (int)((1e5) +` 100);
//int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
int max(int a, int b) {if (a > b) return a; else return b;}
int min(int a, int b) {if (a < b) return a; else return b;}



vector<int> solve3(int n) {
	vi r;
	if (n % 2 == 0 and n % 4 != 0) {
		r.pb(2);
		r.pb(n / 2 - 1);
		r.pb(n / 2 - 1);
	} else if (n % 2 != 0) {
		r.pb(1);
		r.pb(n / 2);
		r.pb(n / 2);
	} else if (n % 4 == 0) {
		r.pb(n / 2);
		r.pb(n / 4);
		r.pb(n / 4);
	}
	return r;
}
void solve() {

	int n, k;
	cin >> n >> k;

	vi added = solve3(n - k + 3);

	for (int i = 0; i < k; i++) {
		cout << (i < 3 ? added[i] : 1) << " ";
	}
	cout << endl;

}
int32_t main()
{

	fio;

#ifndef ONLINE_JUDGE
	freopen("ci.txt", "r", stdin);
	freopen("co.txt", "w", stdout);
#endif

	tc(t) {
		solve();
	}
}