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}$$$.
// Problem: Expression Evaluation Error
// https://codeforces.com/contest/1567/problem/D
// This submission: 
//
// There exists an optimal solution with `n - 1` values that are powers of 10 (in base 10),
// and only one value that is not a power of 10.
//
// Suppose `a` is an optimal solution. So, `sum(a[x], 0 <= x <= n - 1) = s` (in base 10) and
// `sum(a[x], 0 <= x <= n - 1)` (in base 11) is maximum.
// Suppose there exists `a[x]` that is not a power of 10 for `0 <= x <= n - 2`.
// Then, let `a[x][i]` be any non-zero digit and set `b` to be another solution:
// `b[k] = a[k]` for `k != x and k != (n - 1)`.
// `b[x] = a[x]`, except `b[x][i] = a[x][i] - 1`.
// `b[n - 1] = a[n - 1]`, except `b[n - 1][i] = a[n - 1][i] + 1`.
// So, `b` is identical to `a` except we moved `1` at place `i` from `a[x]` to `a[n - 1]`.
// Since `a[x]` is not a power of 10, `b[x]` is positive.
// In case `b[n - 1][i] >= 10`, we can apply a carry (in base 10):
// `b[n - 1][i] <-- b[n - 1][i] - 10`.
// `b[n - 1][i - 1] <-- b[n - 1][i - 1] + 1` (assumes most significant digit placed first).
// This produces identical sum `s` (in base 10) because we computed the carry in base 10, but
// increases the sum (in base 11) because we managed to carry with a sum of 10 instead of 11 at
// place `i`. This contradicts that `a` is an optimal solution.
// So, we must have `b[n - 1][i] <= 9`.
//
// By applying the exchange above repeatedly, we can turn each `a[x]` to a power of 10 for
// `0 <= x <= n - 2`, without losing optimality.
//
// Then, if the sum of digits of `s` is at least `n`, we can split off `n - 1` powers of 10
// from `s` and form `n` values.
// If the sum of digits of `s` is less than `n`, we need to borrow (in base 10) at a place `i` so
// we can create more numbers (of powers of 10). The borrow operation will reduce the sum
// (in base 11) by `1` at place `i`, and increase it only by `10` in the next significant place
// (because we borrowed in base 10). So, we should borrow from the least significant digit
// possible.

import java.util.*;

public class ExpressionEvaluationError {

  // Returns the sum of values in `v`.
  private static int sum(int[] v) {
    return Arrays.stream(v).reduce(0, Integer::sum);
  }

  // Returns the integer value for digits in `v`, with the most significant digit first.
  private static int getValue(int[] v) {
    int result = 0;
    for (int x : v) {
      result = (10 * result) + x;
    }
    return result;
  }

  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);

    int testCasesCount = in.nextInt();
    for (int testCase = 1; testCase <= testCasesCount; ++testCase) {
      int sum = in.nextInt();
      int n = in.nextInt();

      int[] v = new int[10];
      for (int i = v.length - 1; i >= 0; --i) {
        v[i] = (sum % 10);
        sum /= 10;
      }

      // Need to borrow (from the least significant digit) if we don't have enough to
      // make powers of 10s.
      int digitsSum = sum(v);
      while (digitsSum < n) {
        // Start with `i = 8`, because it is not possible to borrow from the ones place (`i = 9`).
        for (int i = 8; i >= 0; --i) {
          if (v[i] > 0) {
            v[i + 1] += 10;
            v[i]--;
            digitsSum += 9;
            break;
          }
        }
      }

      String space = "";
      StringBuilder output = new StringBuilder();
    
      // Produce values that are powers of 10 from digits in `v`.
      for (int k = 0; k < n - 1; ++k) {
        for (int i = v.length - 1; i >= 0; --i) {
          if (v[i] > 0) {
            int[] r = new int[v.length];
            r[i] = 1;
            v[i]--;

            output.append(space + getValue(r));
            space = " ";
            break;
          }
        }
      }

      output.append(space + getValue(v));
      System.out.println(output.toString());
    }

    in.close();
  }
}
