#include <algorithm>
#include <bitset>
#include <cinttypes>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>



#include <iostream>
#include <iterator>
#include <string>
#include <tuple>
#include <utility>

namespace cm
{


class logger
{
public:
  logger(std::ostream &) {}
  logger &set_ostream(std::ostream &)
  {
    return *this;
  }
  logger &set_sep(const std::string &)
  {
    return *this;
  }
  logger &assert_push_enable()
  {
    return *this;
  }
  logger &assert_push_disable()
  {
    return *this;
  }
  logger &assert_exit()
  {
    return *this;
  }
  logger &assert_noexit()
  {
    return *this;
  }
  logger &endl()
  {
    return *this;
  }
  template <class... T>
  logger &log(T...)
  {
    return *this;
  }
  template <class T>
  logger &hint(T...)
  {
    return *this;
  }
  template <class... T>
  logger &operator()(T...)
  {
    return *this;
  }
  template <class... T>
  logger &assert_(T...)
  {
    return *this;
  }
};


namespace impl
{
logger cm_logger(std::cout);
}

} // namespace cm

// clang-format off
#define see(...)
#define asee(...)
#define cm_assert(...)
// clang-format on

// #include "/home/jack/cm/intm.hpp"
// #include "/home/jack/cm/math_util.hpp"

#include <cctype>
#include <cstdio>

namespace cm
{

template <class _Type, size_t _buf_size>
class buffer_reader
{
protected:
  FILE        *src;
  _Type *const buff;
  _Type       *buff_end;
  _Type       *buff_pos;

  void _flush()
  {
    buff_end = buff + fread(buff, sizeof(_Type), _buf_size, src);
    buff_pos = buff;
    if (buff_end == buff)
    {
      *buff_end = '\n';
      buff_end++;
    }
  }

public:
  explicit buffer_reader(FILE *_src) : src(_src), buff(new _Type[_buf_size])
  {
    _flush();
  }

  buffer_reader(const buffer_reader &) = delete;
  buffer_reader(buffer_reader &&)      = delete;
  buffer_reader &operator=(const buffer_reader &) = delete;
  buffer_reader &operator=(buffer_reader &&) = delete;

  _Type get() const
  {
    return *buff_pos;
  }
  _Type next()
  {
    _Type result = get();
    buff_pos++;
    if (buff_pos == buff_end)
      _flush();
    return result;
  }

  ~buffer_reader()
  {
    if (src != stdin)
      fclose(src);
    delete[] buff;
  }
};

template <class _BufferReader>
class scanner : protected _BufferReader
{
private:
  using _BufferReader::get;
  using _BufferReader::next;
  inline bool _is_ws(char c)
  {
    return c <= ' ';
  }
  inline bool _is_cr(char c)
  {
    return c == '\n' || c == '\r';
  }

  int _get_sign()
  {
    while (!isdigit(get()) && get() != '-')
      next();
    if (get() == '-')
      return next(), -1;
    return 1;
  }

public:
  scanner() = delete;
  using _BufferReader::_BufferReader;

  char next_char()
  {
    while (_is_ws(get()))
      next();
    return next();
  }

  char *next_token(char *s)
  {
    while (_is_ws(get()))
      next();
    while (!_is_ws(get()))
      *s++ = next();
    *s = '\0';
    return s;
  }

  char *next_line(char *s)
  {
    while (_is_ws(get()))
      next();
    while (!_is_cr(get()))
      *s++ = next();
    *s = '\0';
    return s;
  }

  template <class _Integer>
  _Integer next_integer()
  {
    _Integer sign = _get_sign();
    _Integer result(0);
    while (isdigit(get()))
      result = result * _Integer(10) + _Integer(next() - '0');
    return sign * result;
  }

  int next_int()
  {
    return next_integer<int>();
  }

  long long next_long()
  {
    return next_integer<long long>();
  }

  double next_double()
  {
    int    sign   = _get_sign();
    double result = 0;
    while (isdigit(get()))
      result = result * 10 + (next() - '0');
    if (get() == '.')
    {
      next();
      double cur_ep = 0.1;
      while (isdigit(get()))
        result += cur_ep * (next() - '0'), cur_ep *= 0.1;
    }
    return sign * result;
  }
};

} // namespace cm


namespace cm
{
using optimal_reader = buffer_reader<char, 1 << 16>;
}

#define DEFINE_SCANNER(sc, filename)                                           \
  cm::scanner<cm::optimal_reader> sc(fopen(filename, "r"));


// #include "/home/jack/cm/segment_tree.hpp"
// #include "/home/jack/cm/string.hpp"

#include <array>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

namespace cm
{

template <class T>
inline bool check_min(T &a, const T &b)
{
  return b < a ? a = b, 1 : 0;
}
template <class T>
inline bool check_max(T &a, const T &b)
{
  return a < b ? a = b, 1 : 0;
}

struct once_t
{
  bool _once = true;
  bool operator()()
  {
    return _once ? (_once = false, true) : false;
  }
};

template <class T, class vt = std::vector<std::vector<T>>>
vt vec_transpose(const vt &v)
{
  size_t n = v.size();
  size_t m = v[0].size();


  vt r(m, std::vector<T>(n));
  for (size_t i = 0; i < n; i++)
    for (size_t j = 0; j < m; j++)
      r[j][i] = v[i][j];

  return r;
}

template <class value_type = int>
struct counter_t
{
private:
  value_type _value{};

public:
  value_type operator()()
  {
    return _value++;
  }

  value_type size() const
  {
    return _value;
  }

  void clear()
  {
    _value = value_type{};
  }
};

namespace impl
{
template <class T, std::size_t n0, std::size_t... n1>
struct __array
{
  using type = std::array<typename __array<T, n1...>::type, n0>;
};

template <class T, std::size_t n0>
struct __array<T, n0>
{
  using type = std::array<T, n0>;
};

} // namespace impl

template <class T, std::size_t... n0>
using array = typename impl::__array<T, n0...>::type;

#if __cplusplus >= 201402L

template <class F>
struct y_combinate_t
{
  F f;

  template <class... Args>
  decltype(auto) operator()(Args &&...args) const
  {
    return f(*this, std::forward<Args>(args)...);
  }
};

template <class F>
y_combinate_t<std::decay_t<F>> y_combinate(F &&f)
{
  return {std::forward<F>(f)};
};

auto vec_take(size_t id)
{
  return [id](const auto &v) { return v[id]; };
}

template <class F, class... T>
auto vec_map(F &&f, const std::vector<T> &...v)
{
  using mapped_t = decltype(f(std::declval<T>()...));

  std::size_t n = [](auto x, auto...) { return x; }(v.size()...);

  std::vector<mapped_t> r;
  r.reserve(n);

  cm::y_combinate([&](auto &&self, std::size_t cnt, auto... its) -> void {
    if (cnt > 0)
    {
      r.emplace_back(f((*its)...));
      self(cnt - 1, std::next(its)...);
    }
  })(n, v.begin()...);

  return r;
}

template <class F>
auto mapper(F &&f)
{
  return [f](auto v) { return vec_map(f, v); };
}

template <class T>
auto transfer(T &&v)
{
  return std::forward<T>(v);
}
template <class T, class F0, class... F1>
auto transfer(T &&v, F0 &&f0, F1 &&...f1)
{
  return transfer(f0(std::forward<T>(v)), f1...);
}

#endif

} // namespace cm

using cm::check_max;
using cm::check_min;

#define CONSTRAINT(n, a, b) constexpr auto n = a;

#include <algorithm>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>

cm::scanner<cm::optimal_reader> sc(stdin);

int main()
{
  int t = sc.next_int();
  for (int i = 0; i < t; i++)
  {
    int n = sc.next_int();
    int k = sc.next_int();

    std::vector<std::pair<int, int>> ps;
    for (int i = 0; i < n; i++)
    {
      int x = sc.next_int();
      int y = sc.next_int();
      ps.emplace_back(x, y);
    }

    auto dis = [&](int x, int y) {
      int dx = ps[x].first - ps[y].first;
      int dy = ps[x].second - ps[y].second;
      return (int64_t)dx * dx + (int64_t)dy * dy;
    };

    std::vector<int> keys{0};
    while ((int)keys.size() < k)
    {
      std::vector<int64_t> mdis;
      for (int i = 0; i < n; i++)
      {
        int64_t cur = std::numeric_limits<int64_t>::max();
        for (int k: keys)
          cm::check_min(cur, dis(k, i));
        mdis.emplace_back(cur);
      }

      int vkey
          = (int)(std::max_element(mdis.begin(), mdis.end()) - mdis.begin());
      keys.push_back(vkey);
    }

    std::vector<int> col;
    for (int i = 0; i < n; i++)
    {
      int64_t cmin_v = std::numeric_limits<int64_t>::max();
      int     cmin_i = -1;
      for (int ki = 0; ki < k; ki++)
        if (cm::check_min(cmin_v, dis(i, keys[ki])))
          cmin_i = ki;
      col.push_back(cmin_i);
    }

    for (int i = 0; i < n; i++)
      printf("%d ", col[i] + 1);
    puts("");
  }
  return 0;
}