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:
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <memory.h>
#include <list>
#include <numeric>
#include <functional>
#include <complex>
#include <cassert>
#include <regex>
#include <random>
#include <iomanip>

using LL = unsigned long long;

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pii pair<int,int> 
#define pll pair<LL,LL> 
#define vi vector<int>
#define vll vector<LL>
#define vvll vector<vector<LL>>
#define vpii vector<pii>
#define vvi vector<vector<int>>
#define forn(it,from,to) for(int (it)=from; (it)<to; (it)++)
const int  INF = 2 * 1000 * 1000 * 1000;
LL MOD = 1e9 + 7;
LL LINF = (LL)4e18;
double EPS = 1e-7;

using namespace std;


LL m, n, q, x, k, y, l, r, t, d, a, b, f;

LL gcd(LL a, LL b) {
	return b ? gcd(b, a % b) : a;
}

LL lcm(LL a, LL b)
{
	return a / gcd(a, b) * b;
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(10);

	cin >> t;

	vll p2 = { 2 };
	while (p2.back() < 1e9) p2.push_back(2ll * p2.back());

	forn(ii, 0, t)
	{
		cin >> n >> k;

		if ((n - k + 2) % 2 == 0)
		{
			forn(i, 0, k - 2) cout << 1 << " ";
			cout << (n - k + 2) / 2 << " " << (n - k + 2) / 2 << endl;
		}
		else
		{
			forn(i, 0, k - 3) cout << 1 << " ";
			n = n - k + 3;
			forn(i, 0, p2.size())
			{
				LL cur = p2[i], cur2 = 2ll * cur;
				if (cur > n) break;
				if ((n - cur) % cur2 == 0 || cur % ((n - cur) / 2) == 0)
				{
					cout << cur << " " << (n - cur) / 2 << " " << (n - cur) / 2 << endl;
					break;
				}
			}
		}
	}

	return 0;
}