On the board, Bob wrote n positive integers in [base](https://en.wikipedia.org/wiki/Positional_notation#Base_of_the_numeral_system) 10 with sum s (i. e. in decimal numeral system). Alice sees the board, but accidentally interprets the numbers on the board as base-11 integers and adds them up (in base 11).

What numbers should Bob write on the board, so Alice's sum is as large as possible?

Input

The input consists of multiple test cases. The first line contains an integer t (1 ≤ t ≤ 100) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers s and n (1 ≤ s ≤ 10^9; 1 ≤ n ≤ min(100, s)) — the sum and amount of numbers on the board, respectively. Numbers s and n are given in decimal notation (base 10).

Output

For each test case, output n positive integers — the numbers Bob should write on the board, so Alice's sum is as large as possible. If there are multiple answers, print any of them.

Example

Input


6
97 2
17 1
111 4
100 2
10 9
999999 3


Output


70 27 
17 
3 4 100 4
10 90
1 1 2 1 1 1 1 1 1 
999900 90 9

Note

In the first test case, 70_{10} + 27_{10} = 97_{10}, and Alice's sum is $$$70_{11} + 27_{11} = 97_{11} = 9 ⋅ 11 + 7 = 106_{10}. (Here x_b represents the number x in base b.) It can be shown that it is impossible for Alice to get a larger sum than 106_{10}$$$.

In the second test case, Bob can only write a single number on the board, so he must write 17.

In the third test case, 3_{10} + 4_{10} + 100_{10} + 4_{10} = 111_{10}, and Alice's sum is $$$3_{11} + 4_{11} + 100_{11} + 4_{11} = 110_{11} = 1 ⋅ 11^2 + 1 ⋅ 11 = 132_{10}. It can be shown that it is impossible for Alice to get a larger sum than 132_{10}$$$.
import java.io.*;
import java.util.*;

public class Solution {
    static FastScanner fs;
    static PrintWriter pw;
    public static void main(String[] args) {
        fs = new FastScanner();
        pw = new PrintWriter(System.out);
        precomp();
        int t = fs.nextInt();
        while (t-- > 0)
            solve();
        pw.close();
    }
    public static void precomp() {

    }
    public static void solve() {
        double s = fs.nextInt()+.1;
        int n = fs.nextInt();
        int[] a = new int[10];
        for (int i=9; i>=0; i--) {
            while (s>Math.pow(10, i)) {
                a[i]++;
                s-=Math.pow(10, i);
            }
        }
        while (true) {
            int sum = 0;
            for (int i : a)
                sum += i;
            if (sum >= n) {
                for (int j=0; j<n-1; j++) {
                    for (int i=0; i<10; i++) {
                        if (a[i]!=0) {
                            pw.print(1);
                            for (int k=0; k<i; k++)
                                pw.print(0);
                            pw.print(' ');
                            a[i]--;
                            break;
                        }
                    }
                }
                int last = 0;
                for (int i=0; i<10; i++)
                    last += a[i] * Math.pow(10, i);
                pw.println(last);
                return;
            }
            for (int i=1; i<10; i++) {
                if (a[i]!=0) {
                    a[i]--;
                    a[i-1]+=10;
                    break;
                }

            }
        }
    }
    static class pair {
        long lo, hi;
        pair (long x, long y) {lo=x; hi=y;}

    }
    static long pow(long b, long exp, long mod) {
        long ret = 1;
        while (exp > 0) {
            if ((exp & 1) > 0)
                ret = (ret * b) % mod;
            b = (b * b) % mod;
            exp >>= 1;
        }
        return ret;
    }
    //    static int k;
//    static int par(int curr) {
//        return (1<<k)-1-(((1<<k)-1-curr)/2);
//    }
//    static int left(int curr) {
//        return (1<<k)-1-(2*((1<<k)-1-curr)+1);
//    }
//    static int right(int curr) {
//        return (1<<k)-1-(2*((1<<k)-1-curr));
//    }
    static int gcd(int a, int b) {
        if (a == 0) return b;
        return gcd(b % a, a);
    }

    static void ruffleSort(int[] a) {
        int n = a.length;//shuffle, then sort
        for (int i = 0; i < n; i++) {
            int oi = random.nextInt(n), temp = a[oi];
            a[oi] = a[i];
            a[i] = temp;
        }
        Arrays.sort(a);
    }

    static final Random random = new Random();

    static class FastScanner {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");

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

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

        int[] readArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

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

    static int[] reverse(int[] a) {
        int n = a.length;
        int[] res = new int[n];
        for (int i = 0; i < n; i++) res[i] = a[n - 1 - i];
        return res;
    }
    static class Node {
        int sum;
        int min;
        //Here We store the value that will be propagated lazily
        Integer pendingVal = null;
        int from;
        int to;

        int size() {
            return to - from + 1;
        }

    }
    static class SegmentTree {

        private Node[] heap;
        private int[] array;
        private int size;

        /**
         * Time-Complexity:  O(n*log(n))
         *
         * @param array the Initialization array
         */
        public SegmentTree(int[] array) {
            this.array = Arrays.copyOf(array, array.length);
            //The max size of this array is about 2 * 2 ^ log2(n) + 1
            size = (int) (2 * Math.pow(2.0, Math.floor((Math.log((double) array.length) / Math.log(2.0)) + 1)));
            heap = new Node[size];
            build(1, 0, array.length);
        }


        public int size() {
            return array.length;
        }

        //Initialize the Nodes of the Segment tree
        private void build(int v, int from, int size) {
            heap[v] = new Node();
            heap[v].from = from;
            heap[v].to = from + size - 1;

            if (size == 1) {
                heap[v].sum = array[from];
                heap[v].min = array[from];
            } else {
                //Build childs
                build(2 * v, from, size / 2);
                build(2 * v + 1, from + size / 2, size - size / 2);

                heap[v].sum = heap[2 * v].sum + heap[2 * v + 1].sum;
                //min = min of the children
                heap[v].min = Math.min(heap[2 * v].min, heap[2 * v + 1].min);
            }
        }

        /**
         * Range Sum Query
         *
         * Time-Complexity: O(log(n))
         *
         * @param  from from index
         * @param  to to index
         * @return sum
         */
        public int rsq(int from, int to) {
            return rsq(1, from, to);
        }

        private int rsq(int v, int from, int to) {
            Node n = heap[v];

            //If you did a range update that contained this node, you can infer the Sum without going down the tree
            if (n.pendingVal != null && contains(n.from, n.to, from, to)) {
                return (to - from + 1) * n.pendingVal;
            }

            if (contains(from, to, n.from, n.to)) {
                return heap[v].sum;
            }

            if (intersects(from, to, n.from, n.to)) {
                propagate(v);
                int leftSum = rsq(2 * v, from, to);
                int rightSum = rsq(2 * v + 1, from, to);

                return leftSum + rightSum;
            }

            return 0;
        }

        /**
         * Range Min Query
         *
         * Time-Complexity: O(log(n))
         *
         * @param  from from index
         * @param  to to index
         * @return min
         */
        public int rMinQ(int from, int to) {
            return rMinQ(1, from, to);
        }

        private int rMinQ(int v, int from, int to) {
            Node n = heap[v];


            //If you did a range update that contained this node, you can infer the Min value without going down the tree
            if (n.pendingVal != null && contains(n.from, n.to, from, to)) {
                return n.pendingVal;
            }

            if (contains(from, to, n.from, n.to)) {
                return heap[v].min;
            }

            if (intersects(from, to, n.from, n.to)) {
                propagate(v);
                int leftMin = rMinQ(2 * v, from, to);
                int rightMin = rMinQ(2 * v + 1, from, to);

                return Math.min(leftMin, rightMin);
            }

            return Integer.MAX_VALUE;
        }


        /**
         * Range Update Operation.
         * With this operation you can update either one position or a range of positions with a given number.
         * The update operations will update the less it can to update the whole range (Lazy Propagation).
         * The values will be propagated lazily from top to bottom of the segment tree.
         * This behavior is really useful for updates on portions of the array
         * <p>
         * Time-Complexity: O(log(n))
         *
         * @param from  from index
         * @param to    to index
         * @param value value
         */
        public void update(int from, int to, int value) {
            update(1, from, to, value);
        }

        private void update(int v, int from, int to, int value) {

            //The Node of the heap tree represents a range of the array with bounds: [n.from, n.to]
            Node n = heap[v];

            /**
             * If the updating-range contains the portion of the current Node  We lazily update it.
             * This means We do NOT update each position of the vector, but update only some temporal
             * values into the Node; such values into the Node will be propagated down to its children only when they need to.
             */
            if (contains(from, to, n.from, n.to)) {
                change(n, value);
            }

            if (n.size() == 1) return;

            if (intersects(from, to, n.from, n.to)) {
                /**
                 * Before keeping going down to the tree We need to propagate the
                 * the values that have been temporally/lazily saved into this Node to its children
                 * So that when We visit them the values  are properly updated
                 */
                propagate(v);

                update(2 * v, from, to, value);
                update(2 * v + 1, from, to, value);

                n.sum = heap[2 * v].sum + heap[2 * v + 1].sum;
                n.min = Math.min(heap[2 * v].min, heap[2 * v + 1].min);
            }
        }

        //Propagate temporal values to children
        private void propagate(int v) {
            Node n = heap[v];

            if (n.pendingVal != null) {
                change(heap[2 * v], n.pendingVal);
                change(heap[2 * v + 1], n.pendingVal);
                n.pendingVal = null; //unset the pending propagation value
            }
        }

        //Save the temporal values that will be propagated lazily
        private void change(Node n, int value) {
            n.pendingVal = value;
            n.sum = n.size() * value;
            n.min = value;
            array[n.from] = value;

        }

        //Test if the range1 contains range2
        private boolean contains(int from1, int to1, int from2, int to2) {
            return from2 >= from1 && to2 <= to1;
        }
        //check inclusive intersection, test if range1[from1, to1] intersects range2[from2, to2]
        private boolean intersects(int from1, int to1, int from2, int to2) {
            return from1 <= from2 && to1 >= from2   //  (.[..)..] or (.[...]..)
                    || from1 >= from2 && from1 <= to2; // [.(..]..) or [..(..)..
        }
    }
}