#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

#define unordered_map __fast_unordered_map
template<class Key, class Value, class Hash = std::hash<Key>>
using unordered_map = __gnu_pbds::gp_hash_table<Key, Value, Hash>;

template<class C> void mini(C &a4, C b4) { a4 = min(a4, b4); }
template<class C> void maxi(C &a4, C b4) { a4 = max(a4, b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream &operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto vv : V) os << vv << ","; return os << "]";
}
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

int have_testcases_from, have_testcases_to;

const LD kPi = 2 * acos(0);

struct CD {
  LD re, im;
  CD operator=(LD a) { re = a; im = 0; return *this; }
  CD operator*(CD& z) { return {re * z.re - im * z.im, re * z.im + im * z.re}; }
  void operator*=(CD& z) { *this = (*this * z); }
  CD operator+(CD& z) { return {re + z.re, im + z.im}; }
  CD operator-(CD& z) { return {re - z.re, im - z.im}; }
  void operator/=(LD f) { re /= f; im /= f; }
};

int powMod(int a, int n, int p) {
  int res = 1;
  while (n) {
    if (n & 1) { res = ((LL)res * a) % p; }
    n >>= 1; a = ((LL)a * a) % p;
  }
  return res;
}

struct FFT {
private:
  CD *A, *B, *tmp, *res, *omega;
  int *perm;
  int maxh;
  // not needed if this is going to be used just once
  void Clear(int n) {
    REP (i, n) { A[i] = B[i] = res[i] = tmp[i] = 0; }
  }
  
  void fft(CD* from, CD* to, int depth, bool inv){
    int N = (1 << depth);
    for (int i = 0; i < N; i++) { to[perm[i] >> (maxh - depth)] = from[i]; }
    RE (m, depth) {
      int step = 1 << m;
      for (int pos = 0; pos < N; pos += step){
        int cur = 0;
        int delta = 1 << (maxh - m);
        if (!inv) { cur = 1 << maxh; delta *= -1; }
        CD *lft = to + pos, *rgt = lft + step / 2;
        REP (k, step / 2) {
          CD a = *lft, b = omega[cur] * *rgt;
          *lft++ = a + b; *rgt++ = a - b;
          cur += delta;
        }
      }
    }

    if (inv) { REP (i, N) { to[i] /= N; } }
  }
  
public:
  FFT(int deg) {
    maxh = 0; int N = 1, h = -1;
    while (N <= 2 * deg) { maxh++; N *= 2; }
    deg = N + 20;
    A = new CD[deg];
    B = new CD[deg];
    res = new CD[deg];
    tmp = new CD[deg];
    omega = new CD[deg];
    perm = new int[deg];
    LD ang = 2 * kPi / N;
    REP (i, N + 1) { omega[i] = {cos(i * ang), sin(i * ang)}; }
    perm[0] = 0;
    RE (i, N - 1) {
      if ((i & (i - 1)) == 0) { h++; }
      perm[i] = perm[i ^ (1 << h)] | (1 << (maxh - h - 1));
    }
  }
  VI mul_less_exact(VI Q, VI R) {
    int depth = 0, size = 1;
    int N = SZ(Q) + SZ(R) - 1;
    while (size < N) { depth++; size *= 2; }
    Clear(size);
    copy(ALL(Q), A); copy(ALL(R), B);
    fft(A, res, depth, false);
    fft(B, tmp, depth, false);
    REP (i, size) tmp[i] *= res[i];
    fft(tmp, res, depth, true);
    VI ans;
    REP (i, N) { ans.PB((long long)round(res[i].re)); }
    return ans;
  }
  
  VI Prepare(VI& v, int base, int bpow) {
    VI ans;
    for (int x : v) { ans.PB(bpow ? x / base : x % base); }
    return ans;
  }
  int Sum(VI& v, int P) { // debug/assert purposes only
    return accumulate(ALL(v), 0LL) % P;
  }
  VI mul_exact(VI Q, VI R) {
    int base = 32000;
    LL pows[] = {1, base, (int)1LL * base * base};
    VI ans(SZ(Q) + SZ(R) - 1);
    REP (q, 2) {
      VI W = Prepare(Q, base, q);
      REP (r, 2) {
        VI V = Prepare(R, base, r);
        VI C = mul_less_exact(W, V);
        REP (i, SZ(C)) { ans[i] = (ans[i] + 1LL * C[i] * pows[q + r]); }
      }
    }
    return ans;
  }
};

FFT global_fft(30 * 1000 + 50);
const LL Infty = 4e18;

struct Testcase {
  int tidx_;

  Testcase(int idx) : tidx_(idx) {}

  int N;
  vector<LL> vals_minus, vals_plus;

  void Input() {
    cin >> N;
    for (int i = 0; i < N; ++i) {
      int h;
      cin >> h;
      if (h > 0)
        vals_plus.push_back(h);
      else
        vals_minus.push_back(h);
    }
  }

  vector<LL> SolvePlusForSuffixes(vector<LL> plus) {
    sort(ALL(plus));
    debug(plus);

    const vector<int> mul_with_first =
      global_fft.mul_exact(plus, plus);

    debug(mul_with_first);

    vector<LL> answer(SZ(plus) + 1);

    for (int len = 2; len <= SZ(plus); ++len) {
      answer[len] = answer[len - 1] + plus[0] * plus[len - 1];
      if (len % 2 == 0)
        mini(answer[len], mul_with_first[len - 1] / 2);
    }

    answer[1] = Infty;
    return answer;
  }

  LL SolvePlusOnly() {
    return SolvePlusForSuffixes(vals_plus)[SZ(vals_plus)];
  }

  LL SolvePlusMinus() {
    sort(ALL(vals_plus));
    sort(ALL(vals_minus));

    debug(vals_plus, vals_minus);

    LL answer = Infty;
    const vector<LL> minus_without_first =
      vector<int>(vals_minus.begin() + 1, vals_minus.end());

    vector<LL> convs_plus_minus =
      global_fft.mul_exact(minus_without_first, vals_plus);
    convs_plus_minus.insert(convs_plus_minus.begin(), 0LL);

    debug(convs_plus_minus);

    int M = SZ(vals_minus);
    int P = SZ(vals_plus);
    vector<LL> best_for_suffix(M + 1, Infty);
    if (M >= P) {
      best_for_suffix[P] = 0;
      for (int i = 0; i < P; ++i)
        best_for_suffix[P] += vals_plus[i] * vals_minus[P - i - 1];
    }


    {
      LL increase = 0;
      for (int num_small = 1; num_small <= P; ++num_small) {
        if (num_small >= 1)
          increase += vals_minus[0] * vals_plus[P - num_small];
        const int num_paired = P - num_small;
        if (num_paired + 1 > M) { continue; }
        debug(num_small, num_paired, best_for_suffix);
        mini(best_for_suffix[num_paired + 1],
             convs_plus_minus[num_paired] + increase);
        debug(num_small, num_paired, best_for_suffix);
      }
    }

    vector<LL> minus_revved(ALL(vals_minus));
    for (int &x : minus_revved) { x = -x; }
    vector<LL> best_for_prefix = SolvePlusForSuffixes(minus_revved);

    debug(best_for_prefix, best_for_suffix);

    for (int len_prefix = 0; len_prefix <= M; ++len_prefix)
      mini(answer, best_for_prefix[len_prefix] + best_for_suffix[M - len_prefix]);

    if (M >= 2)
      mini(answer, best_for_prefix[2] + best_for_suffix[M - 1]);
    
    return answer;
  }

  void Run() {
    Input();
    LL result = 0;
    if (tidx_ < have_testcases_from || tidx_ > have_testcases_to) { return; }

    if (vals_minus.empty()) {
      result = SolvePlusOnly();
    } else if (vals_plus.empty()) {
      for (int x : vals_minus)
        vals_plus.push_back(-x);
      vals_minus.clear();
      result = SolvePlusOnly();
    } else {
      result = SolvePlusMinus();
    }

    cout << "Case #" << tidx_ << ": " << result << "\n";
  }
};

int32_t main(int32_t argc, char **argv) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);

  int T;
  cin >> T;

  if (argc > 1) {
    assert(argc == 3);
    const int thread_idx = atoi(argv[1]);
    const int thread_num = atoi(argv[2]);
    assert(0 <= thread_idx && thread_idx < thread_num);
    have_testcases_from = (thread_idx * T) / thread_num + 1;
    have_testcases_to = ((thread_idx + 1) * T) / thread_num;
  } else {
    have_testcases_from = 1;
    have_testcases_to = T;
  }

  for (int i = 1; i <= T; ++i)
    Testcase(i).Run();
}