#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>

namespace impl
{

inline void force_templates()
{
#define FORCE(type)                                                            \
  {                                                                            \
    [[maybe_unused]] auto f = [] type {};                                      \
  }

  FORCE((std::pair<int, int>))
  FORCE((std::vector<int>))
  FORCE((std::vector<std::pair<int, int>>))

#undef FORCE
}

} // namespace impl


#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 <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();

    std::vector<int> as(n);
    for (int i = 0; i < n; i++)
      as[i] = sc.next_int();

    int m = *std::max_element(as.begin(), as.end()) + 1;

    auto [first_hop, next_hop] = [&] {
      std::vector<int> last(m, n);

      std::vector<std::vector<int>> a(n);
      for (int i = n - 1; i >= 0; i--)
      {
        a[i] = {last.begin(), last.begin() + as[i]};
        std::fill(last.begin(), last.begin() + as[i], i);
      }

      return std::make_pair(std::move(last), std::move(a));
    }();

    auto pre2_sum = [&] {
      std::vector<int> a(n + 2);

      a[n + 1] = 0;
      a[n]     = 0;
      for (int i = n - 1; i >= 0; i--)
        a[i] = as[i] + a[i + 2];

      return a;
    }();

    for (int thr = 1; thr < m; thr++)
    {
      int cb = 0;
      int cs = 0;

      auto trans_below = [&](int l, int r) {
        int il = l + cb;
        int ir = (r % 2 == il % 2) ? r : r + 1;
        cs += pre2_sum[il] - pre2_sum[ir];
        cb = ir - r;
      };

      auto trans_above = cm::y_combinate([&](auto &&self, int v) -> void {
        if (cb == 1)
        {
          cb = 0;
          self(v - thr);
        }
        else
        {
          int vq = (v - 1) / thr;
          cs += ((vq + 1) / 2) * thr;
          if (vq % 2 == 0)
          {
            cs += (v - 1) % thr + 1;
            cb = 1;
          }
          else
          {
            cb = 0;
          }
        }
      });

      int p = first_hop[thr];
      trans_below(0, p);
      for (; p != n; p = next_hop[p][thr])
      {
        // see(p);
        trans_above(as[p]);
        trans_below(p + 1, next_hop[p][thr]);
      }

      printf("%d\n", cs);
    }
  }
  return 0;
}