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.*;

/**
 * A simple template for competitive programming problems.
 */
public class Solution {
    //InputReader in = new InputReader("input.txt");
    final InputReader in = new InputReader(System.in);

    final PrintWriter out = new PrintWriter(System.out);

    void solve() {
        int t = in.nextInt();
        while(t-->0) {
            int s = in.nextInt();
            int n = in.nextInt();
            List<Integer> l = parcala(s, n);
            for(int k : l) {
                out.print(k + " ");
            }
            out.println();
        }
    }

    private List<Integer> parcala(int s, int n) {
        List<Integer> digits = new ArrayList<>();
        while(s!=0) {
            digits.add(s%10);
            s/=10;
        }
        int sd = 0;
        for(int k : digits) {
            sd += k;
        }
        List<Integer> ans = new ArrayList<>();
        int diff = n - sd;
        while(diff>0) {
            for(int i=1; i<digits.size(); i++) {
                while(digits.get(i)>0) {
                    diff -= 9;
                    digits.set(i, digits.get(i)-1);
                    digits.set(i-1, digits.get(i-1)+10);
                    if(diff<=0) break;
                }
                if(diff<=0) break;
            }
        }
        List<Integer> basdegs = new ArrayList<>();
        int mul = 1;
        for(int i=0; i<digits.size(); i++) {
            for(int j=0; j<digits.get(i); j++) {
                basdegs.add(mul);
            }
            mul *= 10;
        }
        Collections.reverse(basdegs);
        for(int i=0; i<n-1; i++) {
            ans.add(basdegs.get(i));
        }
        int sum = 0;
        for(int i=n-1; i<basdegs.size(); i++) {
            sum += basdegs.get(i);
        }
        ans.add(sum);
        return ans;
    }

    public class UnionFind {
        private final int[] component;
        private final int[] size;
        private int componentCount;

        /**
         * Initially each object is only connected to itself.
         */
        public UnionFind(int numObjects) {
            component = new int[numObjects];
            size = new int[numObjects];
            componentCount = numObjects;
            for (int i = 0; i < numObjects; i++) {
                component[i] = i;
                size[i] = 1;
            }
        }

        /**
         * Returns the component ID of the object.
         */
        public int find(int p) {
            if (p < 0 || p >= component.length) throw new IllegalArgumentException("Illegal object ID.");
            int root = p;
            while (component[root] != root)
                root = component[root];
            while (root != component[p]) {
                int next = component[p];
                component[p] = root;
                p = next;
            }
            return root;
        }

        /**
         * Merges the components of the objects.
         */
        public void union(int p, int q) {
            if (p < 0 || p >= component.length) throw new IllegalArgumentException("Illegal object ID.");
            if (q < 0 || q >= component.length) throw new IllegalArgumentException("Illegal object ID.");
            p = find(p);
            q = find(q);
            if (p == q) return;
            componentCount--;
            if (size[p] < size[q]) {
                component[p] = q;
                size[q] += size[p];
            } else {
                component[q] = p;
                size[p] += size[q];
            }
        }

        /**
         * Returns true if the objects are in the same component, false otherwise.
         */
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }

        /**
         * Returns the size of the component p belong to.
         */
        public int componentSize(int p) {
            return size[find(p)];
        }

        /**
         * Returns the number of components.
         */
        public int count() {
            return componentCount;
        }
    }

    private void shuffle(int[] a) {
        int n = a.length;
        Random random = new Random();
        random.nextInt();
        for (int i = 0; i < n; i++) {
            int change = i + random.nextInt(n - i);
            swap(a, i, change);
        }
    }

    private static void swap(int[] a, int i, int j) {
        int helper = a[i];
        a[i] = a[j];
        a[j] = helper;
    }

    public static void main(final String[] args) throws FileNotFoundException {
        final Solution s = new Solution();
        final Long t1 = System.currentTimeMillis();
        s.solve();
        System.err.println(System.currentTimeMillis() - t1 + " ms");
        s.out.close();
    }

    public Solution() throws FileNotFoundException {
    }

    private static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        Random r = new Random();
        InputReader(final InputStream stream) {
            this.stream = stream;
        }

        InputReader(final String fileName) {
            InputStream stream = null;
            try {
                stream = new FileInputStream(fileName);
            } catch (final FileNotFoundException e) {
                e.printStackTrace();
            }
            this.stream = stream;
        }

        int[] nextArray(final int n) {
            final int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = nextInt();
            return arr;
        }

        int[][] nextMatrix(final int n, final int m) {
            final int[][] matrix = new int[n][m];
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    matrix[i][j] = nextInt();
            return matrix;
        }

        String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            final StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            final StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

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

        private int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (final IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        private boolean isSpaceChar(final int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(final int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }

}