/**
 * @file A.cpp
 * @author georgeyucjr ([email protected])
 * @brief
 * @version 998244353.1145141919810
 * @date 2024-04-19
 *
 * @copyright Copyright (c) 2024
 *
 */
#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE
#define LOCAL
#endif

#if __cplusplus >= 201100LL
#else
#error Please use C++11 Or Higher CPP version
#endif

using ll = long long;
using ull = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using arr3 = std ::array<int, 3>;
using arr4 = std ::array<int, 4>;
using pii = std ::pair<int, int>;

#if __cplusplus >= 201400LL
#define rep(i, f, t, ...) for (std ::decay<decltype(f + t)>::type i = f, _END_##i = t, ##__VA_ARGS__; i <= _END_##i; ++i)
#define per(i, f, t, ...) for (std ::decay<decltype(f + t)>::type i = f, _END_##i = t, ##__VA_ARGS__; i >= _END_##i; --i)
#else
#define rep(i, f, t, ...) for (decltype(f + t) i = f, _END_##i = t, ##__VA_ARGS__; i <= _END_##i; ++i)
#define per(i, f, t, ...) for (decltype(f + t) i = f, _END_##i = t, ##__VA_ARGS__; i >= _END_##i; --i)
#endif

#define emb emplace_back
#define pb push_back
#define mkp make_pair
#define FILEIO(filename) freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout)

#ifndef INLINE_V
#if __cplusplus >= 201700LL
#define INLINE_V inline
#else
#define INLINE_V
#endif
#endif

#if __cplusplus >= 201400LL
#define EXPR constexpr
#else
#define EXPR
#endif

#if __cplusplus >= 201400LL

template <class T, class U>
inline constexpr auto ceil(T &&x, U &&y)
{
  return (x > 0 ? (x + y - 1) / y : x / y);
}

template <class T, class U>
inline constexpr auto floor(T &&x, U &&y)
{
  return (x > 0 ? x / y : (x - y + 1) / y);
}

template <class T, class U>
inline constexpr auto divmod(T &&x, U &&y)
{
  auto &&q = floor(x, y);
  return std ::pair{q, x - q * y};
}

inline constexpr auto sqr(const auto &x) { return x * x; }
inline constexpr auto Max(const auto &x) { return x; }
inline constexpr auto Min(const auto &x) { return x; }
inline constexpr auto Max(const auto &x, const auto &y, const auto &...args) { return x < y ? Max(y, args...) : Max(x, args...); }
inline constexpr auto Min(const auto &x, const auto &y, const auto &...args) { return x < y ? Min(x, args...) : Min(y, args...); }
inline constexpr void chkmax(auto &d, const auto &...x) { d = Max(d, x...); }
inline constexpr void chkmin(auto &d, const auto &...x) { d = Min(d, x...); }

#else

template <class T, class U>
inline T ceil(T &&x, U &&y)
{
  return (x > 0 ? (x + y - 1) / y : x / y);
}

template <class T, class U>
inline T floor(T &&x, U &&y)
{
  return (x > 0 ? x / y : (x - y + 1) / y);
}

template <class T, class U>
inline pair<T, T> divmod(T &&x, U &&y)
{
  T &&q = floor(x, y);
  return std ::make_pair(q, x - q * y);
}

template <class T>
inline T sqr(const T &x) { return x * x; }

template <class T, class... Args>
inline T Max(const T &x, const T &y, const Args &...args)
{
  return x < y ? Max(y, args...) : Max(x, args...);
}

template <class T, class... Args>
inline T Min(const T &x, const T &y, const Args &...args)
{
  return x > y ? Min(y, args...) : Min(x, args...);
}

template <class T, class... Args>
inline T chkmax(T &d, const Args &...x) { d = Max(d, x...); }

template <class T, class... Args>
inline T chkmin(T &d, const Args &...x) { d = Min(d, x...); }

#endif

#define ALL(vc) std ::begin(vc), std ::end(vc)

#if __cplusplus >= 202000LL

template <class T>
  requires(std ::is_signed_v<T> || std ::is_unsigned_v<T>)
INLINE_V constexpr static T inf = std ::numeric_limits<T>::max() >> 1;

template <std ::ranges ::forward_range R>
inline constexpr auto Sum(R &&r)
{
  return std ::accumulate(std ::ranges ::begin(r), std ::ranges ::end(r), 0);
}

template <std ::ranges ::forward_range R, typename T>
inline constexpr auto Sum(R &&r, T init)
{
  return std ::accumulate(std ::ranges ::begin(r), std ::ranges ::end(r), init);
}

template <std ::ranges ::forward_range R>
inline constexpr int SZ(R &&x) { return std ::size(x); }

#else

template <class R>
inline EXPR auto Sum(R &&r)
{
  return std ::accumulate(ALL(r), 0);
}

template <class R, typename T>
inline EXPR auto Sum(R &&r, T init)
{
  return std ::accumulate(ALL(r), init);
}

template <class R>
inline EXPR auto Sum(R f, R t)
{
  return std ::accumulate(f, t);
}

template <class R, typename T>
inline EXPR auto Sum(R f, R t, T init)
{
  return std ::accumulate(f, t, init);
}

template <class T>
inline EXPR int SZ(T &&x) { return static_cast<int>(x.size()); }

template <class T>
INLINE_V constexpr static T inf = std ::numeric_limits<T>::max() >> 1;

#endif

template <class Os, class T>
inline Os &operator<<(Os &os, T &t)
{
  for (auto ele : t)
    os << ele << " ";
  os << "\n";
  return os;
}

template <class T>
inline constexpr void clr_cont(T &cont)
{
  T nw;
  cont.swap(nw);
}

#ifndef __GEORGEYUCJR_READ__
#define __GEORGEYUCJR_READ__

#if __cplusplus >= 202000LL && !defined(MACOS) && defined(__unix__)

#define CHECK_EOF 0
#if CHECK_EOF
#define ECHK0 *ptr ? *ptr++ : -1
#define ECHK1   \
  if (ch == -1) \
    return set(false), *this;
#define ECHK2 \
  if (!*ptr)  \
    return set(false), *this;
#define ECHK3 and ch != -1
#define ECHK4 and*ptr
#else
#define ECHK0 *ptr++
#define ECHK1
#define ECHK2
#define ECHK3
#define ECHK4
#endif

#if !defined(MACOS)
#define USE_MMAP
#include <sys/mman.h>
#include <sys/stat.h>
#endif

#if __cpluspls >= 202000LL && !defined(MACOS)
#define DISABLE_RANGE
#endif

#if CHECK_EOF || !defined(USE_MMAP)
#define EV -1
#else
#define EV 0
#endif

namespace FastIO
{
  template <typename T>
  struct make_unsigned : public std ::make_unsigned<T>
  {
  };
  template <>
  struct make_unsigned<i128>
  {
    using type = u128;
  };
  template <typename T>
  concept tupleLike = requires(T t) { std ::tuple_size_v<decltype(std ::tuple_cat(t))>; };

  inline constexpr ull pw10(int t) { return t == 0 ? 1 : pw10(t - 1) * 10; }

  std ::mt19937 mrand(std ::random_device{}());
  std ::mt19937_64 mrand64(std ::random_device{}());

  inline constexpr static std ::size_t bufSize = 1 << 20;

  class IO;
  class In
  {
    friend class IO;

  private:
    FILE *inFile;
    bool status = true;
#ifdef USE_MMAP
    struct stat st;
    char *ptr;
    int fd;
#elif !defined(LOCAL)
    char buf[bufSize], *p1, *p2;
#endif

  public:
#ifdef LOCAL
    inline int getch() { return fgetc_unlocked(inFile); }
    inline void input(FILE *f) { inFile = f, set(); }
#elif defined(USE_MMAP)
    inline int getch() { return ECHK0; }
    inline void input(FILE *f)
    {
      inFile = f;
      if (inFile)
        fd = fileno(inFile), fstat(fd, &st), ptr = (char *)mmap(nullptr, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0), set();
    }
    static constexpr auto n = []()
    {
      std ::array<uint32_t, 0x10000> n{};
      for (int i = 0; i != 0x10000; ++i)
        n[i] = -1;
      constexpr uint32_t e0 = 0x01, e1 = 0x100;
      int x = 0;
      for (uint32_t i = 0, c0 = 0x3030; i != 10; i++, c0 += e0)
        for (uint32_t j = 0, c1 = c0; j != 10; j++, c1 += e1)
          n[c1] = x++;
      return n;
    }();
#else
    inline int getch() { return (p1 == p2 ? (p2 = (p1 = buf) + fread(buf, 1, bufSize, inFile)) : 0), p1 == p2 ? -1 : *p1++; }
    inline void input(FILE *f) { inFile = f, p1 = p2 = buf, set(); }
#endif
    inline void input(const char *s) { input(fopen(s, "rb")); }
    inline void set(bool s = true) { status = s; }
    inline bool get() const { return status; }
  };
  class Out
  {
    friend class IO;

  public:
    FILE *outFile;
#ifndef LOCAL
    char pbuf[bufSize], *pp;
#endif

  public:
#ifdef LOCAL
    inline void flush() { outFile ? fflush(outFile) : 0; }
    inline void putch(char c) { fputc_unlocked(c, outFile); }
#else
    inline void flush() { (outFile ? fwrite(pbuf, 1, pp - pbuf, outFile), fflush(outFile) : 0), pp = pbuf; }
    inline void putch(char c) { ((pp - pbuf == bufSize) ? fwrite(pbuf, 1, bufSize, outFile), pp = pbuf : 0), *pp++ = c; }
#endif
    inline void output(const char *s) { flush(), outFile = fopen(s, "wb"); }
    inline void output(FILE *f) { flush(), outFile = f; }
  };
  class IO : public In, public Out
  {
  private:
    std ::size_t precision = 12;

  public:
    IO(FILE * = nullptr, FILE * = nullptr);
    ~IO() { flush(); }
    static constexpr bool blank(char);
    template <typename... Args>
      requires(sizeof...(Args) > 1)
    IO &read(Args &...);
    template <typename T>
      requires(std ::is_signed_v<T> && std ::is_integral_v<T>) || std ::is_same_v<std ::decay_t<T>, i128>
    IO &read(T &);
    template <typename T>
      requires(std ::is_unsigned_v<T> && std ::is_integral_v<T>) || std ::is_same_v<std ::decay_t<T>, u128>
    IO &read(T &);
    template <typename T>
      requires std ::is_floating_point_v<T>
    IO &read(T &);
    template <typename T>
    T read();
    IO &read(char &);
    IO &read(char *);
    IO &read(std ::string &);
    IO &readline(char *);
    IO &readline(std ::string &);
    template <tupleLike T>
    IO &read(T &&);
    template <std ::ranges::input_range R>
    IO &read(R &&r) { return readArray(std ::forward<R>(r)); }
    void setprecision(std ::size_t n = 6u) { precision = n; }
    template <typename... Args>
      requires(sizeof...(Args) > 1)
    void write(Args &&...);
    inline void write() const {}
    template <typename T>
      requires(std ::is_signed_v<T> && std ::is_integral_v<T>) || std ::is_same_v<std ::decay_t<T>, i128>
    void write(T);
    template <typename T>
      requires(std ::is_unsigned_v<T> && std ::is_integral_v<T>)
    void write(T);
    void write(u128);
    inline void write(char);
    template <typename T>
      requires std ::is_floating_point_v<T>
    void write(T);
    inline void write(bool);
    void write(char *);
    void write(const char *);
    void write(const std ::string &);
    template <typename T>
    void write(std ::initializer_list<T>);
    template <tupleLike T>
    void write(T &&);
    template <std ::ranges::input_range R>
    void write(R &&);
    template <typename... Args>
    void writeln(Args &&...);
    template <typename T>
    inline void writespc(T &&x);
    operator bool() const { return get(); }
  } io(stdin, stdout);
  template <typename... Args>
  inline void writeln(Args &&...x) { io.writeln(std ::forward<Args>(x)...); }
  template <typename T>
  inline void writeln(std ::initializer_list<T> x) { io.writeln(x); }
#pragma endregion

#define isdigit(x) ((x) >= '0' && (x) <= '9')
  IO::IO(FILE *in, FILE *out) { input(in), output(out); }
  constexpr bool IO::blank(char c) { return c == ' ' || c == '\n' || c == '\r'; }
  template <typename... Args>
    requires(sizeof...(Args) > 1)
  IO &IO::read(Args &...args)
  {
    if constexpr (CHECK_EOF)
      (read(args) && ...);
    else
      (read(args), ...);
    return *this;
  }
  template <typename T>
    requires(std ::is_signed_v<T> && std ::is_integral_v<T>) || std ::is_same_v<std ::decay_t<T>, i128>
  IO &IO::read(T &x)
  {
    x = 0;
    static typename make_unsigned<T>::type t;
    bool sign = false;
#ifndef USE_MMAP
    int ch = getch();
    while (!isdigit(ch) ECHK3)
      sign = (ch == '-'), ch = getch();
    ECHK1
    t = 0;
    while (isdigit(ch))
      t = t * 10 + (ch ^ 48), ch = getch();
#else
    while (!isdigit(*ptr) ECHK4)
      sign = *ptr++ == '-';
    ECHK2
    t = *ptr++ ^ 48;
    while (~n[*reinterpret_cast<std ::uint16_t *&>(ptr)])
      t = t * 100 + n[*reinterpret_cast<std ::uint16_t *&>(ptr)++];
    if (isdigit(*ptr))
      t = t * 10 + (*ptr++ ^ 48);
#endif
    x = sign ? (~t + 1) : t;
    return *this;
  }
  template <typename T>
    requires(std ::is_unsigned_v<T> && std ::is_integral_v<T>) || std ::is_same_v<std ::decay_t<T>, u128>
  IO &IO::read(T &x)
  {
    x = 0;
#ifndef USE_MMAP
    int ch = getch();
    while (!isdigit(ch) ECHK3)
      ch = getch();
    ECHK1
    while (isdigit(ch))
      x = (x << 1) + (x << 3) + (ch ^ 48), ch = getch();
#else
    while (!isdigit(*ptr) ECHK4)
      ptr++;
    ECHK2
    x = *ptr++ ^ 48;
    while (~n[*reinterpret_cast<std ::uint16_t *&>(ptr)])
      x = x * 100 + n[*reinterpret_cast<std ::uint16_t *&>(ptr)++];
    if (isdigit(*ptr))
      x = x * 10 + (*ptr++ ^ 48);
#endif
    return *this;
  }
  template <typename T>
    requires std ::is_floating_point_v<T>
  IO &IO::read(T &x)
  {
    x = 0;
    T t = 1;
    bool sign = false;
    int ch = getch();
    while (!isdigit(ch) ECHK3)
      sign = (ch == '-'), ch = getch();
    ECHK1
    while (isdigit(ch))
      x = x * 10 + (ch ^ 48), ch = getch();
    if (ch == '.')
      for (ch = getch(); isdigit(ch); ch = getch())
        x += (t /= 10) * (ch ^ 48);
    x = sign ? -x : x;
    return *this;
  }
  template <typename T>
  T IO::read()
  {
    static std ::decay_t<T> x;
    return read(x), x;
  }
  IO &IO::read(char &ch)
  {
    do
      ch = getch();
    while (blank(ch));
    ECHK1
    return *this;
  }
  IO &IO::read(char *s)
  {
    int ch = getch();
    while (blank(ch))
      ch = getch();
    ECHK1
    while (!blank(ch) && ch != EV)
      *s++ = ch, ch = getch();
    *s = 0;
    return *this;
  }
  IO &IO::read(std ::string &s)
  {
    int ch = getch();
    while (blank(ch))
      ch = getch();
    ECHK1
    s.erase();
    while (!blank(ch) && ch != EV)
      s.append(1, ch), ch = getch();
    return *this;
  }
  IO &IO::readline(char *s)
  {
    char *t = s;
    int ch = getch();
    while (ch != '\n' && ch != EV)
      *s++ = ch, ch = getch();
    *s = 0;
    if (s == t && ch != '\n')
      set(false);
    return *this;
  }
  IO &IO::readline(std ::string &s)
  {
    s.erase();
    int ch = getch();
    while (ch != '\n' && ch != EV)
      s.append(1, ch), ch = getch();
    if (s.empty() && ch != '\n')
      set(false);
    return *this;
  }
  template <tupleLike T>
  IO &IO::read(T &&t)
  {
    std ::apply([&](auto &...t)
                { (read(t), ...); },
                t);
    return *this;
  }
  template <typename... Args>
    requires(sizeof...(Args) > 1)
  void IO::write(Args &&...args)
  {
    (write(std ::forward<Args>(args)), ...);
  }
  template <typename T>
    requires(std ::is_signed_v<T> && std ::is_integral_v<T>) || std ::is_same_v<std ::decay_t<T>, i128>
  void IO::write(T x)
  {
    static typename make_unsigned<T>::type y;
    y = x;
    if (x < 0)
      putch('-'), write(~y + 1);
    else
      write(y);
  }
  constexpr auto D = []()
  {
    constexpr uint32_t e0 = 0x1, e1 = 0x100, e2 = 0x10000, e3 = 0x1000000;
    std ::array<uint32_t, 10000> m{};
    int x = 0;
    for (uint32_t i = 0, c0 = 0x30303030; i != 10; i++, c0 += e0)
      for (uint32_t j = 0, c1 = c0; j != 10; j++, c1 += e1)
        for (uint32_t k = 0, c2 = c1; k != 10; k++, c2 += e2)
          for (uint32_t l = 0, c3 = c2; l != 10; l++, c3 += e3)
            m[x++] = c3;
    return m;
  }();
  template <typename T>
    requires(std ::is_unsigned_v<T> && std ::is_integral_v<T>)
  void IO::write(T x)
  {
#ifndef LOCAL
    if (std ::end(pbuf) - pp < 64)
      flush();

    auto L = [&](int x)
    { return x == 1 ? 0 : pw10(x - 1); };
    auto R = [&](int x)
    { return pw10(x) - 1; };

#define de(t)                                               \
  case L(t)... R(t):                                        \
    *reinterpret_cast<uint32_t *>(pp) = D[x / pw10((t)-4)]; \
    pp += 4;                                                \
    x %= pw10((t)-4);

    ull y = x;
    switch (y)
    {
      de(18);
      de(14);
      de(10);
      de(6);
    case L(2)... R(2):
      *reinterpret_cast<uint32_t *>(pp) = D[x * 100];
      pp += 2;
      break;

      de(17);
      de(13);
      de(9);
      de(5);
    case L(1)... R(1):
      *pp = static_cast<char>('0' + x);
      pp += 1;
      break;

    default:
      *reinterpret_cast<uint32_t *>(pp) = D[x / pw10(16)];
      pp += 4;
      x %= pw10(16);
      de(16);
      de(12);
      de(8);
    case L(4)... R(4):
      *reinterpret_cast<uint32_t *>(pp) = D[x];
      pp += 4;
      break;

      de(19);
      de(15);
      de(11);
      de(7);
    case L(3)... R(3):
      *reinterpret_cast<uint32_t *>(pp) = D[x * 10];
      pp += 3;
      break;
    }
#else
    write(u128(x));
#endif
  }
  constexpr u128 _pw10(int x) { return x == 0 ? 1 : _pw10(x - 1) * 10; }
  void IO::write(u128 x)
  {
    if (std ::end(pbuf) - pp < 64)
      flush();
    constexpr auto pw10 = _pw10;
    auto L = [&](int x)
    { return x == 1 ? 0 : pw10(x - 1); };
    auto R = [&](int x)
    { return pw10(x) - 1; };

#define de(t)                                               \
  case L(t)... R(t):                                        \
    *reinterpret_cast<uint32_t *>(pp) = D[x / pw10((t)-4)]; \
    pp += 4;                                                \
    x %= pw10((t)-4);

    switch (x)
    {
      de(38);
      de(34);
      de(30);
      de(26);
      de(22);
      de(18);
      de(14);
      de(10);
      de(6);
    case L(2)... R(2):
      *reinterpret_cast<uint32_t *>(pp) = D[x * 100];
      pp += 2;
      break;

      de(37);
      de(33);
      de(29);
      de(25);
      de(21);
      de(17);
      de(13);
      de(9);
      de(5);
    case L(1)... R(1):
      *pp = static_cast<char>('0' + x);
      pp += 1;
      break;

      de(36);
      de(32);
      de(28);
      de(24);
      de(20);
      de(16);
      de(12);
      de(8);
    case L(4)... R(4):
      *reinterpret_cast<uint32_t *>(pp) = D[x];
      pp += 4;
      break;

    default:
      *reinterpret_cast<uint32_t *>(pp) = D[x / pw10(35)];
      pp += 4;
      x %= pw10(35);
      de(35);
      de(31);
      de(27);
      de(23);
      de(19);
      de(15);
      de(11);
      de(7);
    case L(3)... R(3):
      *reinterpret_cast<uint32_t *>(pp) = D[x * 10];
      pp += 3;
      break;
    }
  }
  void IO::write(bool x) { putch(x ^ 48); }
  void IO::write(char c) { putch(c); }
  template <typename T>
    requires std ::is_floating_point_v<T>
  void IO::write(T x)
  {
    static char buf[512];
    *std ::to_chars(buf, buf + 512, x, std ::chars_format::fixed, precision).ptr = 0;
    write(buf);
  }
  void IO::write(char *s)
  {
    while (*s)
      putch(*s++);
  }
  void IO::write(const char *s)
  {
    while (*s)
      putch(*s++);
  }
  void IO::write(const std ::string &s) { write(s.data()); }
  template <typename T>
  void IO::write(std ::initializer_list<T> t)
  {
    auto first = std ::begin(t), last = std ::end(t);
    if (first != last)
      for (write(*first++); first != last; ++first)
      {
        putch(' ');
        write(*first);
      }
  }
  template <tupleLike T>
  void IO::write(T &&t)
  {
    [&]<std ::size_t... I>(std ::index_sequence<I...>)
    {
      (..., (I == 0 ? void(0) : putch(' '), write(std ::get<I>(t))));
    }(std ::make_index_sequence<std ::tuple_size_v<std ::remove_reference_t<T>>>());
  }
  template <std ::ranges::input_range R>
  void IO::write(R &&r)
  {
    if constexpr (std ::is_same_v<std ::decay_t<R>, std ::string>)
      return write(r.data());
    auto first = std ::ranges::begin(r), last = std ::ranges::end(r);
    if (first != last)
      for (write(*first++); first != last; ++first)
      {
        putch(' ');
        write(*first);
      }
  }
  template <typename... Args>
  void IO::writeln(Args &&...x) { write(std ::forward<Args>(x)...), putch('\n'); }
  template <typename T>
  inline void IO::writespc(T &&x) { write(x), putch('\n'); }
} // namespace FastIO
using namespace FastIO;

#else

#ifndef LUOGU
#define auto_att __attribute__((target("avx2"), optimize(3, "Ofast", "unroll-loops", "inline")))
#else
#define auto_att
#endif

namespace FastIO
{
#define endl '\n'
  INLINE_V static constexpr size_t buf_size = 1 << 18;
  INLINE_V static constexpr size_t integer_size = 20;
  INLINE_V static constexpr size_t block_size = 10000;

  static char inbuf[buf_size + 1] = {};
  static char outbuf[buf_size + 1] = {};
  static char block_str[block_size * 4 + 1] = {};

  static constexpr uint64_t power10[] = {1,
                                         10,
                                         100,
                                         1000,
                                         10000,
                                         100000,
                                         1000000,
                                         10000000,
                                         100000000,
                                         1000000000,
                                         10000000000,
                                         100000000000,
                                         1000000000000,
                                         10000000000000,
                                         100000000000000,
                                         1000000000000000,
                                         10000000000000000,
                                         100000000000000000,
                                         1000000000000000000,
                                         10000000000000000000u};

  struct Scanner
  {
#ifndef LOCAL
  private:
    size_t pos, end;

    inline void load()
    {
      end = fread(inbuf, 1, buf_size, stdin);
      inbuf[end] = '\0';
    }
    inline void reload()
    {
      size_t len = end - pos;
      memmove(inbuf, inbuf + pos, len);
      end = len + fread(inbuf + len, 1, buf_size - len, stdin);
      inbuf[end] = '\0';
      pos = 0;
    }
    inline void skip_space()
    {
      while (inbuf[pos] <= ' ')
      {
        if (__builtin_expect(++pos == end, 0))
          reload();
      }
    }
    inline char get_next() { return inbuf[pos++]; }
    inline char get_next_nonspace()
    {
      skip_space();
      return inbuf[pos++];
    }

  public:
    Scanner() { load(); }

    auto_att inline void read(char &c) { c = get_next_nonspace(); }
    auto_att inline void read(std ::string &s)
    {
      skip_space();
      s = "";
      do
      {
        size_t start = pos;
        while (inbuf[pos] > ' ')
          ++pos;
        s += std ::string(inbuf + start, inbuf + pos);
        if (inbuf[pos] != '\0')
          break;
        reload();
      } while (true);
    }

    template <class T>
    typename std ::enable_if<std ::is_integral<T>::value, void>::type read(T &x)
    {
      char c = get_next_nonspace();
      if (__builtin_expect(pos + integer_size >= end, 0))
        reload();
      bool neg = false;
      if (c == '-')
        neg = true, x = 0;
      else
        x = c & 15;
      while ((c = get_next()) >= '0')
        x = (x << 3) + (x << 1) + (c & 15);
      if (neg)
        x = -x;
    }
#else
    template <typename _Tp>
    inline void read(_Tp &x)
    {
      char ch = getchar();
      int f = 1;
      x = 0;
      for (; ch < '0' || ch > '9'; ch = getchar())
        f = ch == '-' ? -1 : 1;
      for (; ch >= '0' && ch <= '9'; ch = getchar())
        x = (x << 3) + (x << 1) + (ch ^ 48);
      x *= f;
    }
    inline void read(char &c) { c = getchar(); }
    inline void read(char *x)
    {
      int i = 0;
      char c = ' ';
      for (; c <= ' ';)
        c = getchar();
      for (; c > ' ';)
        x[i++] = c, c = getchar();
      x[i] = 0;
    }
    inline void read(std ::string &x)
    {
      x.clear();
      char c = ' ';
      for (; c <= ' ';)
        c = getchar();
      for (; c > ' ';)
        x += c, c = getchar();
    }
#endif
    template <class Head, class... Others>
    void read(Head &head, Others &...others)
    {
      read(head);
      read(others...);
    }
    template <class T1, class T2>
    inline void read(std ::pair<T1, T2> &x) { read(x.first), read(x.second); }
  } is;

  struct Printer
  {
#ifndef LOCAL
  private:
    size_t pos = 0;

    auto_att inline void flush()
    {
      fwrite(outbuf, 1, pos, stdout);
      pos = 0;
    }

    inline void pre_calc()
    {
      for (size_t i = 0; i < block_size; ++i)
      {
        size_t j = 4, k = i;
        while (j--)
        {
          block_str[i * 4 + j] = k % 10 | 48;
          k /= 10;
        }
      }
    }

    static EXPR size_t get_integer_size(uint64_t n)
    {
      if (n >= power10[10])
      {
        if (n >= power10[19])
          return 20;
        if (n >= power10[18])
          return 19;
        if (n >= power10[17])
          return 18;
        if (n >= power10[16])
          return 17;
        if (n >= power10[15])
          return 16;
        if (n >= power10[14])
          return 15;
        if (n >= power10[13])
          return 14;
        if (n >= power10[12])
          return 13;
        if (n >= power10[11])
          return 12;
        return 11;
      }
      else
      {
        if (n >= power10[9])
          return 10;
        if (n >= power10[8])
          return 9;
        if (n >= power10[7])
          return 8;
        if (n >= power10[6])
          return 7;
        if (n >= power10[5])
          return 6;
        if (n >= power10[4])
          return 5;
        if (n >= power10[3])
          return 4;
        if (n >= power10[2])
          return 3;
        if (n >= power10[1])
          return 2;
        return 1;
      }
    }

  public:
    Printer() { pre_calc(); }
    ~Printer() { flush(); }
    inline void write(char c)
    {
      outbuf[pos++] = c;
      if (__builtin_expect(pos == buf_size, 0))
        flush();
    }
    inline void write(const char *s)
    {
      while (*s != 0)
      {
        outbuf[pos++] = *s++;
        if (__builtin_expect(pos == buf_size, 0))
          flush();
      }
    }
    inline void write(const std ::string &s)
    {
      for (auto c : s)
      {
        outbuf[pos++] = c;
        if (__builtin_expect(pos == buf_size, 0))
          flush();
      }
    }

    template <class T>
    typename std ::enable_if<std ::is_integral<T>::value, void>::type write(T x)
    {
      if (__builtin_expect(pos + integer_size >= buf_size, 0))
        flush();
      if (x < 0)
        write('-'), x = -x;
      size_t digit = get_integer_size(x);
      size_t len = digit;
      while (len >= 4)
      {
        len -= 4;
        memcpy(outbuf + pos + len, block_str + ((x % block_size) << 2), 4);
        x /= block_size;
      }
      memcpy(outbuf + pos, block_str + (x << 2) + (4 - len), len);
      pos += digit;
    }
#else
    inline void write(char c) { putchar(c); }
    inline void write(const char *x)
    {
      for (int i = 0; x[i]; ++i)
        write(x[i]);
    }
    inline void write(std::string s)
    {
      for (auto c : s)
        write(c);
    }
    template <typename _Tp>
    inline void write(_Tp x)
    {
      if (x < 0)
        putchar('-'), x = -x;
      if (x > 9)
        write(x / 10);
      putchar(x % 10 ^ 48);
    }
#endif
    template <class Head, class... Others>
    void write(const Head &head, const Others &...others)
    {
      write(head);
      write(' ');
      write(others...);
    }

    template <class... Args>
    void writeln(const Args &...args)
    {
      write(args...);
      write('\n');
    }
    template <class T>
    inline void writespc(const T &x)
    {
      write(x);
      write(" ");
    }
    template <class T1, class T2>
    inline void write(const std ::pair<T1, T2> &x) { write(x.first, x.second); }
  } os;

  struct IO : public Scanner, public Printer 
  {
  } io;
}; // namespace FastIO
using namespace FastIO;
#endif
#endif
using namespace std;

#warning Do not use debug.hpp.

signed main() {
  int T;
  io.read(T);
  while (T--) {
    int n;
    io.read(n);
    vector<int> a(n + 1);
    vector<int> b(n + 1);
    rep(i, 1, n) io.read(a[i]);
    sort(begin(a) + 1, end(a));
    int mid = 0;
    while (mid + 1 <= n && a[mid + 1] <= 0)
      ++mid;
    int l = (1 + mid) / 2, r = l + 1;
    rep(i, 1, mid) {
      if (i & 1)
        b[l] = a[i], --l;
      else
        b[r] = a[i], ++r;
    }
    l = (mid + 1 + n) / 2, r = l + 1;
    per(i, n, mid + 1) {
      if ((n - i + 1) & 1)
        b[l] = a[i], --l;
      else
        b[r] = a[i], ++r;
    }
    if ((b[1] < b[mid]) == (b[mid + 1] < b[n]))
      reverse(begin(b) + 1, begin(b) + mid + 1);
    ll ans = 0;
    rep(i, 1, n)
      ans += 1ll * b[i] * (i == n ? b[1] : b[i + 1]);
    io.writeln(ans);
  }
#if defined(LOCAL) && !defined(CPH)
  cerr << "Spend time : " << clock() * 1. / CLOCKS_PER_SEC * 1000. << "ms\n";
#endif
  return 0;
}