#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using namespace std;
struct matrix {
  int sz;
  long long a[105][105];
  matrix &operator=(const matrix &T) {
    sz = T.sz;
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= sz; j++) {
        a[i][j] = T.a[i][j];
      }
    }
    return *this;
  }
  matrix operator+(const matrix &T) const {
    matrix ans;
    ans.sz = sz;
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= sz; j++) {
        ans.a[i][j] = a[i][j] + T.a[i][j];
        ans.a[i][j] %= (int)(1e9 + 7);
      }
    }
    return ans;
  }
  matrix operator*(const matrix &T) const {
    matrix ans;
    ans.sz = sz;
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= sz; j++) {
        ans.a[i][j] = 0;
        for (int k = 1; k <= sz; k++) {
          ans.a[i][j] += a[i][k] * T.a[k][j];
          ans.a[i][j] %= (int)(1e9 + 7);
        }
      }
    }
    return ans;
  }
  matrix I() {
    matrix ans;
    ans.sz = sz;
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= sz; j++) {
        if (i == j)
          ans.a[i][j] = 1;
        else
          ans.a[i][j] = 0;
      }
    }
    return ans;
  }
  matrix power(long long p) {
    if (p == 0) return I();
    if (p == 1) return *this;
    matrix tmp = power(p / 2);
    if (p % 2)
      tmp = tmp * tmp * (*this);
    else
      tmp = tmp * tmp;
    return tmp;
  }
  void print() {
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= sz; j++) {
        printf(j == sz ? "%lld\n" : "%lld ", a[i][j]);
      }
    }
    return;
  }
};
struct polynomial {
  vector<complex<double> > v;
  int sz;
  polynomial operator*(const polynomial &T) const {
    polynomial ans;
    if (sz >= T.sz) {
      ans = *this;
      for (int i = 0; i < T.sz; i++) {
        ans.v[i] *= T.v[i];
      }
    } else {
      ans = T;
      for (int i = 0; i < sz; i++) {
        ans.v[i] *= v[i];
      }
    }
    return ans;
  }
};
polynomial FFT(polynomial a) {
  if (a.sz <= 1) return a;
  polynomial even, odd;
  even.sz = odd.sz = 0;
  for (int i = 0; i < a.sz; i += 2) {
    even.v.push_back(a.v[i]);
    even.sz++;
  }
  for (int i = 1; i < a.sz; i += 2) {
    odd.v.push_back(a.v[i]);
    odd.sz++;
  }
  polynomial Even = FFT(even);
  polynomial Odd = FFT(odd);
  polynomial ans;
  ans.sz = a.sz;
  for (int i = 0; i < ans.sz; i++) {
    ans.v.push_back(0);
  }
  for (int i = 0; i < a.sz / 2; i++) {
    complex<double> w =
        polar(1.0, -2 * (double)3.14159265358979 * i / a.sz) * Odd.v[i];
    ans.v[i] = Even.v[i] + w;
    ans.v[i + a.sz / 2] = Even.v[i] - w;
  }
  return ans;
}
polynomial IFFT(polynomial a) {
  for (int i = 0; i < a.sz; i++) {
    a.v[i] = conj(a.v[i]);
  }
  polynomial ans = FFT(a);
  for (int i = 0; i < a.sz; i++) {
    ans.v[i] = conj(ans.v[i]);
    ans.v[i] /= ans.sz;
  }
  return ans;
}
struct polygon {
  int n;
  pair<int, int> a[1005];
  double area() {
    double d1 = 0, d2 = 0;
    for (int i = 0; i < n; i++) {
      d1 += a[i].first * a[(i + 1) % n].second;
      d2 += a[(i + 1) % n].first * a[i].second;
    }
    return (d1 - d2) / 2;
  }
  bool inside(pair<long double, long double> p) {
    int ct = 0;
    long double d;
    pair<long double, long double> p1 = a[0];
    for (int i = 1; i <= n; i++) {
      pair<long double, long double> p2 = a[i % n];
      if (p.second > min(p1.second, p2.second) &&
          p.second <= max(p1.second, p2.second) &&
          p.first <= max(p1.first, p2.first) && p1.second != p2.second) {
        d = (p.second - p1.second) * (p2.first - p1.first) /
                (p2.second - p1.second) +
            p1.first;
        if (p1.first == p2.first || p.first <= d) ct++;
      }
      p1 = p2;
    }
    return ct % 2;
  }
};
struct graph {
  int n;
  vector<int> v[1005];
  int vis[1005], low[1005], t;
  int indeg[1005];
  stack<int> st;
  int top = 0;
  bool instack[1005];
  int to[1005];
  void tarjanDFS(int first) {
    vis[first] = low[first] = ++t;
    st.push(first);
    instack[first] = true;
    for (auto i : v[first]) {
      if (!vis[i]) tarjanDFS(i);
      if (instack[i]) {
        low[first] = min(low[first], low[i]);
      }
    }
    if (vis[first] == low[first]) {
      int i;
      do {
        i = st.top();
        st.pop();
        instack[i] = false;
        to[i] = first;
      } while (i != first);
    }
  }
  void tarjan() {
    memset(vis, 0, sizeof(vis));
    t = 0;
    for (int i = 1; i <= n; i++) {
      if (!vis[i]) tarjanDFS(i);
    }
    return;
  }
  void calIndeg() {
    for (int i = 1; i <= n; i++) {
      for (auto j : v[i]) indeg[j]++;
    }
    return;
  }
};
struct segtree {
  int l, r, mid;
  long long val = 0, lazy = 0;
  segtree *lc, *rc;
  segtree(int L, int R) {
    l = L;
    r = R;
    mid = (l + r) / 2;
    if (l != r) {
      lc = new segtree(l, mid);
      rc = new segtree(mid + 1, r);
    }
  }
  void apply(long long X) {
    val += X;
    lazy += X;
  }
  void push() {
    if (l == r) return;
    lc->apply(lazy);
    rc->apply(lazy);
    lazy = 0;
  }
  void update(int L, int R, long long X) {
    push();
    if (l == L && r == R) {
      apply(X);
      return;
    } else if (R <= mid)
      lc->update(L, R, X);
    else if (L >= mid + 1)
      rc->update(L, R, X);
    else {
      lc->update(L, mid, X);
      rc->update(mid + 1, R, X);
    }
    val = min(lc->val, rc->val);
  }
  long long query(int L, int R) {
    push();
    if (l == L && r == R)
      return val;
    else if (R <= mid)
      return lc->query(L, R);
    else if (L >= mid + 1)
      return rc->query(L, R);
    else {
      return min(lc->query(L, mid), rc->query(mid + 1, R));
    }
  }
} * segroot;
mt19937 rng(
    (unsigned int)chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
  uniform_int_distribution<int> uni(l, r);
  return uni(rng);
}
vector<long long> fac, inv;
long long power(long long a, long long p) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = ans * a % (int)(1e9 + 7);
    p >>= 1;
    a = a * a % (int)(1e9 + 7);
  }
  return ans;
}
vector<long long> inverse(int n) {
  vector<long long> ans(n + 1);
  ans[0] = ans[1] = 1;
  for (int i = 2; i <= n; i++) {
    ans[i] = ans[(int)(1e9 + 7) % i] * ((int)(1e9 + 7) - (int)(1e9 + 7) / i) %
             (int)(1e9 + 7);
  }
  return ans;
}
vector<long long> factorial(int n) {
  vector<long long> ans(n + 1);
  ans[0] = ans[1] = 1;
  for (int i = 2; i <= n; i++) {
    ans[i] = ans[i - 1] * i % (int)(1e9 + 7);
  }
  return ans;
}
vector<long long> factorialInverse(int n) {
  vector<long long> inv = inverse(n);
  vector<long long> ans(n + 1);
  ans[0] = ans[1] = 1;
  for (int i = 2; i <= n; i++) {
    ans[i] = inv[i] * ans[i - 1] % (int)(1e9 + 7);
  }
  return ans;
}
long long ncr(int n, int r) {
  return fac[n] * inv[r] % (int)(1e9 + 7) * inv[n - r] % (int)(1e9 + 7);
}
void calfacinv(int n) {
  fac = factorial(n);
  inv = factorialInverse(n);
  return;
}
struct node {
  int first, second;
  bool operator<(const node &T) const { return first < T.first; }
};
int T;
int n;
int a[105], sum;
void solve(int CASE) {
  scanf("%d%d", &(sum), &(n));
  int need = n;
  int tar = 1e9;
  int p = 0;
  int re = sum;
  memset(a, 0, sizeof(a));
  while (true) {
    p++;
    if (p > n) p = 1;
    if (need > 0) need--;
    while (re - tar < need) {
      tar /= 10;
    }
    a[p] += tar;
    re -= tar;
    if (re == 0) break;
  }
  for (int i = 1; i <= n; i++) {
    printf(i == n ? "%d\n" : "%d ", a[i]);
  }
  return;
}
int main() {
  T = 1;
  scanf("%d", &(T));
  for (int _ = 1; _ <= T; _++) {
    solve(_);
  }
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

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}$$$.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using namespace std;
struct matrix {
  int sz;
  long long a[105][105];
  matrix &operator=(const matrix &T) {
    sz = T.sz;
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= sz; j++) {
        a[i][j] = T.a[i][j];
      }
    }
    return *this;
  }
  matrix operator+(const matrix &T) const {
    matrix ans;
    ans.sz = sz;
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= sz; j++) {
        ans.a[i][j] = a[i][j] + T.a[i][j];
        ans.a[i][j] %= (int)(1e9 + 7);
      }
    }
    return ans;
  }
  matrix operator*(const matrix &T) const {
    matrix ans;
    ans.sz = sz;
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= sz; j++) {
        ans.a[i][j] = 0;
        for (int k = 1; k <= sz; k++) {
          ans.a[i][j] += a[i][k] * T.a[k][j];
          ans.a[i][j] %= (int)(1e9 + 7);
        }
      }
    }
    return ans;
  }
  matrix I() {
    matrix ans;
    ans.sz = sz;
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= sz; j++) {
        if (i == j)
          ans.a[i][j] = 1;
        else
          ans.a[i][j] = 0;
      }
    }
    return ans;
  }
  matrix power(long long p) {
    if (p == 0) return I();
    if (p == 1) return *this;
    matrix tmp = power(p / 2);
    if (p % 2)
      tmp = tmp * tmp * (*this);
    else
      tmp = tmp * tmp;
    return tmp;
  }
  void print() {
    for (int i = 1; i <= sz; i++) {
      for (int j = 1; j <= sz; j++) {
        printf(j == sz ? "%lld\n" : "%lld ", a[i][j]);
      }
    }
    return;
  }
};
struct polynomial {
  vector<complex<double> > v;
  int sz;
  polynomial operator*(const polynomial &T) const {
    polynomial ans;
    if (sz >= T.sz) {
      ans = *this;
      for (int i = 0; i < T.sz; i++) {
        ans.v[i] *= T.v[i];
      }
    } else {
      ans = T;
      for (int i = 0; i < sz; i++) {
        ans.v[i] *= v[i];
      }
    }
    return ans;
  }
};
polynomial FFT(polynomial a) {
  if (a.sz <= 1) return a;
  polynomial even, odd;
  even.sz = odd.sz = 0;
  for (int i = 0; i < a.sz; i += 2) {
    even.v.push_back(a.v[i]);
    even.sz++;
  }
  for (int i = 1; i < a.sz; i += 2) {
    odd.v.push_back(a.v[i]);
    odd.sz++;
  }
  polynomial Even = FFT(even);
  polynomial Odd = FFT(odd);
  polynomial ans;
  ans.sz = a.sz;
  for (int i = 0; i < ans.sz; i++) {
    ans.v.push_back(0);
  }
  for (int i = 0; i < a.sz / 2; i++) {
    complex<double> w =
        polar(1.0, -2 * (double)3.14159265358979 * i / a.sz) * Odd.v[i];
    ans.v[i] = Even.v[i] + w;
    ans.v[i + a.sz / 2] = Even.v[i] - w;
  }
  return ans;
}
polynomial IFFT(polynomial a) {
  for (int i = 0; i < a.sz; i++) {
    a.v[i] = conj(a.v[i]);
  }
  polynomial ans = FFT(a);
  for (int i = 0; i < a.sz; i++) {
    ans.v[i] = conj(ans.v[i]);
    ans.v[i] /= ans.sz;
  }
  return ans;
}
struct polygon {
  int n;
  pair<int, int> a[1005];
  double area() {
    double d1 = 0, d2 = 0;
    for (int i = 0; i < n; i++) {
      d1 += a[i].first * a[(i + 1) % n].second;
      d2 += a[(i + 1) % n].first * a[i].second;
    }
    return (d1 - d2) / 2;
  }
  bool inside(pair<long double, long double> p) {
    int ct = 0;
    long double d;
    pair<long double, long double> p1 = a[0];
    for (int i = 1; i <= n; i++) {
      pair<long double, long double> p2 = a[i % n];
      if (p.second > min(p1.second, p2.second) &&
          p.second <= max(p1.second, p2.second) &&
          p.first <= max(p1.first, p2.first) && p1.second != p2.second) {
        d = (p.second - p1.second) * (p2.first - p1.first) /
                (p2.second - p1.second) +
            p1.first;
        if (p1.first == p2.first || p.first <= d) ct++;
      }
      p1 = p2;
    }
    return ct % 2;
  }
};
struct graph {
  int n;
  vector<int> v[1005];
  int vis[1005], low[1005], t;
  int indeg[1005];
  stack<int> st;
  int top = 0;
  bool instack[1005];
  int to[1005];
  void tarjanDFS(int first) {
    vis[first] = low[first] = ++t;
    st.push(first);
    instack[first] = true;
    for (auto i : v[first]) {
      if (!vis[i]) tarjanDFS(i);
      if (instack[i]) {
        low[first] = min(low[first], low[i]);
      }
    }
    if (vis[first] == low[first]) {
      int i;
      do {
        i = st.top();
        st.pop();
        instack[i] = false;
        to[i] = first;
      } while (i != first);
    }
  }
  void tarjan() {
    memset(vis, 0, sizeof(vis));
    t = 0;
    for (int i = 1; i <= n; i++) {
      if (!vis[i]) tarjanDFS(i);
    }
    return;
  }
  void calIndeg() {
    for (int i = 1; i <= n; i++) {
      for (auto j : v[i]) indeg[j]++;
    }
    return;
  }
};
struct segtree {
  int l, r, mid;
  long long val = 0, lazy = 0;
  segtree *lc, *rc;
  segtree(int L, int R) {
    l = L;
    r = R;
    mid = (l + r) / 2;
    if (l != r) {
      lc = new segtree(l, mid);
      rc = new segtree(mid + 1, r);
    }
  }
  void apply(long long X) {
    val += X;
    lazy += X;
  }
  void push() {
    if (l == r) return;
    lc->apply(lazy);
    rc->apply(lazy);
    lazy = 0;
  }
  void update(int L, int R, long long X) {
    push();
    if (l == L && r == R) {
      apply(X);
      return;
    } else if (R <= mid)
      lc->update(L, R, X);
    else if (L >= mid + 1)
      rc->update(L, R, X);
    else {
      lc->update(L, mid, X);
      rc->update(mid + 1, R, X);
    }
    val = min(lc->val, rc->val);
  }
  long long query(int L, int R) {
    push();
    if (l == L && r == R)
      return val;
    else if (R <= mid)
      return lc->query(L, R);
    else if (L >= mid + 1)
      return rc->query(L, R);
    else {
      return min(lc->query(L, mid), rc->query(mid + 1, R));
    }
  }
} * segroot;
mt19937 rng(
    (unsigned int)chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
  uniform_int_distribution<int> uni(l, r);
  return uni(rng);
}
vector<long long> fac, inv;
long long power(long long a, long long p) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = ans * a % (int)(1e9 + 7);
    p >>= 1;
    a = a * a % (int)(1e9 + 7);
  }
  return ans;
}
vector<long long> inverse(int n) {
  vector<long long> ans(n + 1);
  ans[0] = ans[1] = 1;
  for (int i = 2; i <= n; i++) {
    ans[i] = ans[(int)(1e9 + 7) % i] * ((int)(1e9 + 7) - (int)(1e9 + 7) / i) %
             (int)(1e9 + 7);
  }
  return ans;
}
vector<long long> factorial(int n) {
  vector<long long> ans(n + 1);
  ans[0] = ans[1] = 1;
  for (int i = 2; i <= n; i++) {
    ans[i] = ans[i - 1] * i % (int)(1e9 + 7);
  }
  return ans;
}
vector<long long> factorialInverse(int n) {
  vector<long long> inv = inverse(n);
  vector<long long> ans(n + 1);
  ans[0] = ans[1] = 1;
  for (int i = 2; i <= n; i++) {
    ans[i] = inv[i] * ans[i - 1] % (int)(1e9 + 7);
  }
  return ans;
}
long long ncr(int n, int r) {
  return fac[n] * inv[r] % (int)(1e9 + 7) * inv[n - r] % (int)(1e9 + 7);
}
void calfacinv(int n) {
  fac = factorial(n);
  inv = factorialInverse(n);
  return;
}
struct node {
  int first, second;
  bool operator<(const node &T) const { return first < T.first; }
};
int T;
int n;
int a[105], sum;
void solve(int CASE) {
  scanf("%d%d", &(sum), &(n));
  int need = n;
  int tar = 1e9;
  int p = 0;
  int re = sum;
  memset(a, 0, sizeof(a));
  while (true) {
    p++;
    if (p > n) p = 1;
    if (need > 0) need--;
    while (re - tar < need) {
      tar /= 10;
    }
    a[p] += tar;
    re -= tar;
    if (re == 0) break;
  }
  for (int i = 1; i <= n; i++) {
    printf(i == n ? "%d\n" : "%d ", a[i]);
  }
  return;
}
int main() {
  T = 1;
  scanf("%d", &(T));
  for (int _ = 1; _ <= T; _++) {
    solve(_);
  }
  return 0;
}

```