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 ;

//long long int N{100001} ;

// vector <unsigned long long> fac(N) ;
// vector <unsigned long long> inverse_fac(N) ;

// void calc_fact(unsigned long long mod) {
// 	fac[0] = 1;
// 	for (long long int i = 1; i < N; i++)
// 		fac[i] = (fac[i - 1] * i) % mod;
// }
// unsigned long long mod_expo(unsigned long long a, unsigned long long n, unsigned long long mod) {
// 	unsigned long long res{1} ;
// 	a = a % mod;
// 	while (n) {
// 		if (n & 1)
// 			res = (res * a) % mod;
// 		n = n >> 1;
// 		a = (a * a) % mod ;
// 	}
// 	return res % mod;
// }

// unsigned long long modInverse(unsigned long long n, unsigned long long mod) {
// 	return mod_expo(n, mod - 2, mod);
// }

// void calc_inverse_fact(unsigned long long mod) {
// 	inverse_fac[N - 1] = modInverse(fac[N - 1], mod) ;
// 	for (long long int i = N - 2; i >= 0; i--) {
// 		inverse_fac[i] = (inverse_fac[i + 1] * (i + 1)) % mod ;
// 	}
// }

// unsigned long long nCrModPFermat(unsigned long long n, unsigned long long r, unsigned long long mod) {
// 	if (n < r)
// 		return 0;
// 	if (r == 0)
// 		return 1;
// 	unsigned long long res{fac[n]} ;
// 	res = (res * inverse_fac[r]) % mod ;
// 	res = (res * inverse_fac[n - r]) % mod ;
// 	return res ;
// }

// long int num{1000000} ;
// vector <bool> prime(num + 1, true) ;

// void SieveOfEratosthenes(long int n) {
// 	prime[0] = false ;
// 	prime[1] = false ;
// 	for (long int i = 2; i * i <= n; i++) {
// 		if (prime[i] == true) {
// 			for (long int j = i * i; j <= n; j += i)
// 				prime[j] = false;
// 		}
// 	}
// 	return ;
// }

long long int find_spf(long long int n) {
	if (n == 2)
		return 1 ;
	long long int ans{ -1} ;
	for (long long int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0) {
			ans = i ;
			break ;
		}
	}
	return ans ;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin) ;

	freopen("output1.txt", "w", stdout) ;
#endif
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL) ;
	long long int t {} ;
	cin >> t ;
	while (t--) {
		long long int n{}, k{} ;
		cin >> n >> k ;
		while (k != 3) {
			cout << 1 << " " ;
			n-- ;
			k-- ;
		}
		if (n & 1) {
			cout << 1 << " " << (n / 2) << " " << (n / 2) << endl ;
		}
		else {
			if (n % 4 == 0) {
				cout << (n / 4) << " " << (n / 4) << " " << (n / 2) << endl ;
			}
			else if (n % 6 == 0) {
				cout << (n / 3) << " " << (n / 3) << " " << (n / 3) << endl ;
			}
			else {
				n /= 2 ;
				cout << 2 << " " << (2 * (n / 2)) << " " <<  (2 * (n / 2)) << endl ;
			}
		}
	}
	return 0 ;
}