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 JAVA):

Solution:
//package credit;


import java.io.*;
import java.net.CookieHandler;
import java.security.cert.CertificateParsingException;
import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.concurrent.CopyOnWriteArrayList;

public class Main {
    static boolean v[];
    static int ans[];
    int size[];
    static int count = 0;
    static int dsu = 0;
    static int c = 0;
    static int e9 = 1000000007;
    int min = 0;
    int max = Integer.MIN_VALUE;
    long max1 = Long.MIN_VALUE;
    long min1 = Long.MAX_VALUE;
    boolean aBoolean = true;
    boolean y = false;
    long m = 0;
    static boolean t1 = false;

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    int parent[];
    int rank[];
    int n = 0;
    ArrayList<ArrayList<Integer>> arrayLists;
    boolean v1[];
    static boolean t2 = false;
    boolean r = false;
    long fib[];
    long egg[];
    long cb[];
    int min3 = Integer.MAX_VALUE;
    int k = 0;
    Queue<Long> queue;
    HashMap<Long, ArrayList<Long>> hashMap;
    HashMap<Long, Boolean> hashMap1;
    HashMap<Long, Long> hashMap2;
    long p = 0;

    public static void main(String[] args) throws IOException {
        Main g = new Main();
        g.go();
    }

    public void go() throws IOException {
        FastReader scanner = new FastReader();
//            Scanner scanner = new Scanner(System.in);
//            BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
//            String s;
        PrintWriter printWriter = new PrintWriter(System.out);
        int t =scanner.nextInt();
        while (t-- > 0) {
            long n=scanner.nextLong();
            long k=scanner.nextLong();
            k=k-3;
            n=n-k;
            if(n%2!=0){
                long h=n/2;
                for (int i = 0; i < k; i++) {
                    printWriter.print(1+" ");
                }
                printWriter.println(h+" "+h+" "+1);
            }else{
                long o=n/2;
                if(o%2==0){
                    for (int i = 0; i < k; i++) {
                        printWriter.print(1+" ");
                    }
                    printWriter.println(o+" "+(o/2)+" "+(o/2));
                }else{
                    for (int i = 0; i < k; i++) {
                        printWriter.print(1+" ");
                    }
                    printWriter.println((o-1)+" "+(o-1)+" "+2);
                }
            }
        }
        printWriter.flush();
    }
    static final int mod=1_000_000_007;
    public long mul(long a, long b) {
        return a*b;
    }
    public long fact(int x) {
        long ans=1;
        for (int i=2; i<=x; i++) ans=mul(ans, i);
        return ans;
    }
    public long fastPow(long base, long exp) {
        if (exp==0) return 1;
        long half=fastPow(base, exp/2);
        if (exp%2==0) return mul(half, half);
        return mul(half, mul(half, base));
    }
    public long modInv(long x) {
        return fastPow(x, mod-2);
    }
    public long nCk(int n, int k) {
        return mul(fact(n), mul(modInv(fact(k)), modInv(fact(n-k))));
    }
    //    public void sieve(int n){
//        fib=new int[n+1];
//        fib[1]=-1;
//        fib[0]=-1;
//        for (int i =2; i*i<=n; i++) {
//            if(fib[i]==0)
//            for (int j =i*i; j <=n; j+=i){
//                fib[j]=-1;
////                System.out.println("l");
//            }
//        }
//    }
    public void parent(int n){
        parent=new int[n+1];
        size=new int[n+1];
        rank=new int[n+1];
        for (int i = 0; i <=n; i++) {
            parent[i]=i;
            rank[i]=0;
            size[i]=1;
        }
    }
    public void union(int i,int j){
        int root1=find(i);
        int root2=find(j);
//            if(root1 != root2) {
//                parent[root2] = root1;
////                sz[a] += sz[b];
//            }
        if(root1==root2){
            return;
        }
        if(rank[root1]>rank[root2]){
            parent[root2]=root1;
            size[root1]+=size[root2];
        }
        else if(rank[root1]<rank[root2]){
            parent[root1]=root2;
            size[root2]+=size[root1];
        }
        else{
            parent[root2]=root1;
            rank[root1]+=1;
            size[root1]+=size[root2];
        }
    }
    public int find(int p){
        if(parent[p]!=p){
            if(parent[p]==-1){
                return parent[p];
            }
            parent[p]=find(parent[p]);
        }
        return parent[p];
    }
    public double dist(double x1,double y1,double x2,double y2){
        double e=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
        double e1=Math.sqrt(e);
        return e1;
    }
    public void make(int p){
        parent[p]=p;
        rank[p]=1;
    }
    Random rand = new Random();
    public void sort(int[] a, int n) {
        for (int i = 0; i < n; i++) {
            int j = rand.nextInt(i + 1);
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
        Arrays.sort(a, 0, n);
    }
    public long gcd(long a,long b){
        if(b==0){
            return a;
        }
        return gcd(b,a%b);
    }
    public void dfs(ArrayList<Integer> arrayList){
        for (int i = 0; i < arrayList.size(); i++) {
            if(v1[arrayList.get(i)]==false){
                v1[arrayList.get(i)]=true;
                dfs(arrayLists.get(i));
            }
        }
    }
    public double fact(double h){
        double sum=1;
        while(h>=1){
            sum=(sum%e9)*(h%e9);
            h--;
        }
        return sum%e9;
    }
    public long primef(double r){
        long c=0;
        long ans=1;
        while(r%2==0){
            c++;
            r=r/2;
        }
        if(c>0){
            ans*=2;
        }
        c=0;
//            System.out.println(ans+" "+r);
        for (int i = 3; i <=Math.sqrt(r) ;i+=2) {
            while(r%i==0){
//                    System.out.println(i);
                c++;
                r=r/i;
            }
            if(c>0){
                ans*=i;
            }
            c=0;
        }
        if(r>2){
            ans*=r;
        }
        return ans;
    }
    public long divisor(double r){
        long c=0;
        for (int i = 1; i <=Math.sqrt(r); i++) {
            if(r%i==0){
                if(r/i==i){
                    c++;
                }
                else{
                    c+=2;
                }
            }
        }
        return c;
    }
}
class Pair {
    int x;
    String y;
    public Pair(int x, String y) {
        this.x = x;
        this.y = y;
    }
}

// @Override
//    public int hashCode() {
//        int hash =37;
//        return this.x * hash + this.y;
//    }
//    @Override
//    public boolean equals(Object o1){
//        if(o1==null||o1.getClass()!=this.getClass()){
//            return false;
//        }
//        Pair o=(Pair)o1;
//        if(o.x==this.x&&o.y==this.y){
//            return true;
//        }
//        return false;
//    }
//class Sorting implements Comparator<Pair> {
//    public int compare(Pair p1, Pair p2) {
//        if(p1.x==p2.x){
//            return Long.compare(p1.y,p2.y);
//        }else {
//            return -1*Long.compare(p1.x, p2.x);
//        }
//    }
//}