#include <bits/stdc++.h>
using namespace std;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using max_heap = priority_queue<T>;
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
long long binpow(long long base, long long exp) {
  long long mod = 1000000007LL;
  long long res = 1;
  while (exp > 0) {
    if (exp % 2 == 1) res = (res * base) % mod;
    exp = exp >> 1;
    base = (base * base) % mod;
  }
  return res;
}
long long mod(long long x) {
  return ((x % 1000000007LL + 1000000007LL) % 1000000007LL);
}
long long add(long long a, long long b) { return mod(mod(a) + mod(b)); }
long long mul(long long a, long long b) { return mod(mod(a) * mod(b)); }
bool isPrime(long long n) {
  if (n <= 1) return false;
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
const long long N = (long long)1e6;
void sieve(long long N) {
  bool prime[N + 1];
  memset(prime, true, sizeof(prime));
  for (long long p = 2; p * p <= N; p++) {
    if (prime[p] == true) {
      for (long long i = p * p; i <= N; i += p) prime[i] = false;
    }
  }
}
long long fact(long long n) {
  long long res = 1;
  for (long long i = 1; i <= n; i++) {
    res = res * 1ll * i % 1000000007LL;
  }
  return res;
}
long long C(long long n, long long k) {
  return fact(n) * 1ll * binpow(fact(k), 1000000007LL - 2) % 1000000007LL *
         1ll * binpow(fact(n - k), 1000000007LL - 2) % 1000000007LL;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    long long sum, n;
    cin >> sum >> n;
    vector<long long> ans(n, 0);
    long long maxe = (long long)1e9;
    long long i = 0;
    for (long long j = maxe; j >= 1; j = j / 10) {
      while (sum >= j && (sum - j) >= (n - i - 1)) {
        ans[i] += j;
        sum -= j;
        i++;
        if (i == n) {
          i = n - 1;
        }
      }
      if (sum <= 0) {
        break;
      }
    }
    for (long long i = 0; i < n; i++) {
      cout << ans[i] << " ";
    }
    cout << "\n";
  }
  return 0;
}

### Prompt

Your challenge is to write a cpp solution 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>
using namespace std;
template <typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using max_heap = priority_queue<T>;
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
long long binpow(long long base, long long exp) {
  long long mod = 1000000007LL;
  long long res = 1;
  while (exp > 0) {
    if (exp % 2 == 1) res = (res * base) % mod;
    exp = exp >> 1;
    base = (base * base) % mod;
  }
  return res;
}
long long mod(long long x) {
  return ((x % 1000000007LL + 1000000007LL) % 1000000007LL);
}
long long add(long long a, long long b) { return mod(mod(a) + mod(b)); }
long long mul(long long a, long long b) { return mod(mod(a) * mod(b)); }
bool isPrime(long long n) {
  if (n <= 1) return false;
  for (long long i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
const long long N = (long long)1e6;
void sieve(long long N) {
  bool prime[N + 1];
  memset(prime, true, sizeof(prime));
  for (long long p = 2; p * p <= N; p++) {
    if (prime[p] == true) {
      for (long long i = p * p; i <= N; i += p) prime[i] = false;
    }
  }
}
long long fact(long long n) {
  long long res = 1;
  for (long long i = 1; i <= n; i++) {
    res = res * 1ll * i % 1000000007LL;
  }
  return res;
}
long long C(long long n, long long k) {
  return fact(n) * 1ll * binpow(fact(k), 1000000007LL - 2) % 1000000007LL *
         1ll * binpow(fact(n - k), 1000000007LL - 2) % 1000000007LL;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  while (t--) {
    long long sum, n;
    cin >> sum >> n;
    vector<long long> ans(n, 0);
    long long maxe = (long long)1e9;
    long long i = 0;
    for (long long j = maxe; j >= 1; j = j / 10) {
      while (sum >= j && (sum - j) >= (n - i - 1)) {
        ans[i] += j;
        sum -= j;
        i++;
        if (i == n) {
          i = n - 1;
        }
      }
      if (sum <= 0) {
        break;
      }
    }
    for (long long i = 0; i < n; i++) {
      cout << ans[i] << " ";
    }
    cout << "\n";
  }
  return 0;
}

```