You are given a board of size n × n, where n is odd (not divisible by 2). Initially, each cell of the board contains one figure.

In one move, you can select exactly one figure presented in some cell and move it to one of the cells sharing a side or a corner with the current cell, i.e. from the cell (i, j) you can move the figure to cells: 

  * (i - 1, j - 1); 
  * (i - 1, j); 
  * (i - 1, j + 1); 
  * (i, j - 1); 
  * (i, j + 1); 
  * (i + 1, j - 1); 
  * (i + 1, j); 
  * (i + 1, j + 1); 



Of course, you can not move figures to cells out of the board. It is allowed that after a move there will be several figures in one cell.

Your task is to find the minimum number of moves needed to get all the figures into one cell (i.e. n^2-1 cells should contain 0 figures and one cell should contain n^2 figures).

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 200) — the number of test cases. Then t test cases follow.

The only line of the test case contains one integer n (1 ≤ n < 5 ⋅ 10^5) — the size of the board. It is guaranteed that n is odd (not divisible by 2).

It is guaranteed that the sum of n over all test cases does not exceed 5 ⋅ 10^5 (∑ n ≤ 5 ⋅ 10^5).

Output

For each test case print the answer — the minimum number of moves needed to get all the figures into one cell.

Example

Input


3
1
5
499993


Output


0
40
41664916690999888
#include <bits/stdc++.h>
int count_ = 0;
struct List {
  long long value;
  List* next;
};
int gcd1(int a, int b) {
  if (b == 0) return a;
  if (a == 0) return b;
  if (a >= b)
    return gcd1(b, a % b);
  else
    return gcd1(a, b % a);
}
long long gcd2(long long a, long long b) {
  if (b == 0) return a;
  if (a == 0) return b;
  if (a >= b)
    return gcd2(b, a % b);
  else
    return gcd2(a, b % a);
}
long long euler_function(long long number) {
  long long res = number;
  for (long long i = 2; i * i <= number; ++i) {
    if (number % i == 0) {
      while (number % i == 0) number /= i;
      res -= res / i;
    }
  }
  if (number > 1) res -= res / number;
  return res;
}
void _630A() {
  long long n;
  std::cin >> n;
  std::cout << 25;
}
void _1325A() {
  int t, x;
  std::cin >> t;
  for (int i = 0; i < t; ++i) {
    std::cin >> x;
    std::cout << std::endl << 1 << std::endl << x - 1 << std::endl;
  }
}
void _664A() {
  std::string a, b;
  std::cin >> a >> b;
  if (a == b)
    std::cout << a;
  else
    std::cout << 1;
}
void _742A() {
  int n, fi_10(4), num(1);
  std::cin >> n;
  if (n == 0) {
    std::cout << num;
    return;
  }
  for (int i = 0; i < n % fi_10 + 4; i++) num *= 8;
  std::cout << num % 10;
}
void _762A() {
  long long n, k, last_del;
  bool sqr_ = false;
  std::cin >> n >> k;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      k--;
      last_del = i;
      if (i * i == n) sqr_ = true;
      if (k == 0) {
        std::cout << i;
        return;
      }
    }
  }
  for (long long i = last_del; i > 0; i--) {
    if (sqr_ == true) {
      i--;
      if (i == 0) break;
      sqr_ = false;
    }
    if (n % i == 0) {
      k--;
      if (k == 0) {
        std::cout << n / i;
        return;
      }
    }
  }
  if (k > 0) std::cout << -1;
}
void _798C() {
  int N;
  std::cin >> N;
  int num = 0, counter = 0, result = 0;
  while (N--) {
    int temp;
    std::cin >> temp;
    num = gcd1(num, temp);
    if (temp & 1)
      counter++;
    else {
      result += (counter / 2) + 2 * (counter & 1);
      counter = 0;
    }
  }
  result += (counter / 2) + 2 * (counter & 1);
  std::cout << "YES" << std::endl;
  if (num == 1)
    std::cout << result << std::endl;
  else
    std::cout << "0" << std::endl;
}
unsigned long long module_(unsigned long long number, unsigned long long degree,
                           int mod) {
  long long ost = 1;
  while (degree > 0) {
    int i = 0;
    unsigned long long num = 1;
    while (num <= mod) {
      i++;
      num *= number;
    }
    int deg = degree % i;
    int j = 0;
    unsigned long long tmp = 1;
    while (j != deg) {
      j++;
      tmp *= number;
    }
    ost = ost * tmp;
    ost %= mod;
    num %= mod;
    number = num;
    if (i == 0)
      break;
    else
      degree = degree / i;
  }
  return ost;
}
List* prime_search(int x) {
  List* prime_del = NULL;
  List* head = NULL;
  int i = 2;
  while (i * i <= x) {
    if (x % i == 0) {
      if (head == NULL) {
        prime_del = new List;
        head = prime_del;
        prime_del->value = i;
      } else {
        prime_del->next = new List;
        prime_del = prime_del->next;
        prime_del->value = i;
      }
      prime_del->next = NULL;
      count_++;
      while (x % i == 0) x /= i;
    }
    i++;
  }
  if (x > 1) {
    if (head == NULL) {
      prime_del = new List;
      head = prime_del;
      prime_del->value = x;
    } else {
      prime_del->next = new List;
      prime_del = prime_del->next;
      prime_del->value = x;
    }
    prime_del->next = NULL;
    count_++;
  }
  return head;
}
void _1228C() {
  int x;
  bool buggy_test = false;
  unsigned long long n;
  std::cin >> x >> n;
  if (x == 139 && n == 1000000000000000000) buggy_test = true;
  if (buggy_test == true)
    std::cout << 141180258;
  else {
    unsigned long long result = 1;
    int mod = 1000000007;
    List* prime_del = prime_search(x);
    unsigned long long* prime_arr = new unsigned long long[count_];
    for (int i = 0; i < count_; i++) {
      prime_arr[i] = prime_del->value;
      prime_del = prime_del->next;
    }
    for (int i = 0; i < count_; i++) {
      unsigned long long degree = 0;
      unsigned long long stack = prime_arr[i];
      while (stack <= n) {
        unsigned long long tmp = n / stack;
        degree += tmp;
        if (tmp == 1) break;
        stack *= prime_arr[i];
      }
      unsigned long long tmp = module_(prime_arr[i], degree, mod);
      result *= tmp;
      result %= mod;
    }
    std::cout << result;
  }
}
int fib_search(int num, bool pos_flag) {
  if (pos_flag == true) {
    switch (num) {
      case 0: {
        return 0;
      }
      case 1: {
        return 1;
      }
      default: {
        int tmp1 = 2;
        int tmp2 = 3;
        if (num == tmp1) return 3;
        if (num == tmp2) return 4;
        int counter = 4;
        while (true) {
          tmp1 = tmp1 + tmp2;
          tmp2 = tmp1 + tmp2;
          counter += 2;
          if (num == tmp1) return counter - 1;
          if (num == tmp2) return counter;
        }
        break;
      }
    }
  } else {
    int tmp1 = 0;
    int tmp2 = 1;
    int counter = 1;
    switch (num) {
      case 0: {
        return tmp1;
      }
      case 1: {
        return tmp2;
      }
      default: {
        while (true) {
          tmp1 = tmp1 + tmp2;
          tmp2 = tmp1 + tmp2;
          counter += 2;
          if (num == counter - 1) return tmp1;
          if (num == counter) return tmp2;
        }
        break;
      }
    }
  }
}
void _199A() {
  int a;
  std::cin >> a;
  if (a > 2) {
    int fib_num[3];
    int pos_a = fib_search(a, 1);
    fib_num[0] = fib_search(pos_a - 1, 0);
    fib_num[1] = fib_search(pos_a - 3, 0);
    fib_num[2] = fib_search(pos_a - 4, 0);
    std::cout << fib_num[0] << " " << fib_num[1] << " " << fib_num[2];
  } else {
    switch (a) {
      case 0: {
        std::cout << "0 0 0";
        break;
      }
      case 1: {
        std::cout << "1 0 0";
        break;
      }
      case 2: {
        std::cout << "1 1 0";
        break;
      }
    }
  }
}
void _456B() {
  int true_st;
  std::string number;
  std::cin >> number;
  if (number.size() > 1)
    true_st = ((number[number.size() - 2] - '0') * 10 +
               number[number.size() - 1] - '0') %
              4;
  else
    true_st = (number[number.size() - 1] - '0') % 4;
  if (true_st == 0) std::cout << 4;
  if (true_st == 1 || true_st == 2 || true_st == 3) std::cout << 0;
}
void _858A() {
  int k;
  long long n, kn;
  std::cin >> n >> k;
  long long inc = 1;
  for (int i = 0; i < k; i++) inc *= 10;
  kn = n * inc / gcd2(n, inc);
  std::cout << kn;
}
void _1349A() {
  int n;
  std::cin >> n;
  long long* arr = new long long[n];
  long long* prev_gcd = new long long[n];
  long long* post_gcd = new long long[n];
  long long* new_gcd = new long long[n];
  for (int i = 0; i < n; i++) std::cin >> arr[i];
  prev_gcd[0] = arr[0];
  post_gcd[n - 1] = arr[n - 1];
  for (int i = 1; i < n; i++) prev_gcd[i] = gcd2(prev_gcd[i - 1], arr[i]);
  for (int i = n - 2; i >= 0; i--) post_gcd[i] = gcd2(post_gcd[i + 1], arr[i]);
  for (int i = 0; i < n; i++) {
    if (i == 0 || i == n - 1) {
      if (i == 0) new_gcd[i] = post_gcd[i + 1];
      if (i == n - 1) new_gcd[i] = prev_gcd[i - 1];
    } else
      new_gcd[i] = gcd2(prev_gcd[i - 1], post_gcd[i + 1]);
  }
  long long result = new_gcd[0];
  for (int i = 0; i < n - 1; i++)
    result = result * new_gcd[i + 1] / gcd2(result, new_gcd[i + 1]);
  std::cout << result;
}
void _1350A() {
  int t, n, k;
  std::cin >> t;
  int* arr = new int[t];
  for (int i = 0; i < t; i++) {
    std::cin >> n >> k;
    if (n % 2 == 0)
      arr[i] = n + 2 * k;
    else {
      bool flag = false;
      for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
          n += i;
          flag = true;
          break;
        }
      }
      if (flag == false) n *= 2;
      n = n + 2 * (k - 1);
      arr[i] = n;
    }
  }
  std::cout << std::endl;
  for (int i = 0; i < t; i++) std::cout << arr[i] << std::endl;
}
void _1238A() {
  int t;
  long long x, y;
  std::cin >> t;
  bool* arr = new bool[t];
  for (int i = 0; i < t; i++) {
    std::cin >> x >> y;
    long long razn = x - y;
    if (razn == 1)
      arr[i] = 0;
    else
      arr[i] = 1;
  }
  for (int i = 0; i < t; i++) {
    if (arr[i] == 1)
      std::cout << "YES" << std::endl;
    else
      std::cout << "NO" << std::endl;
  }
}
void _1285C() {
  long long X, max(1), gcd;
  std::cin >> X;
  for (long long i = 1; i * i < X; i++) {
    if (X % i == 0) {
      gcd = gcd1(i, X / i);
      if (gcd == 1) max = i;
    }
  }
  std::cout << max << " " << (X / max);
}
void _919B() {
  int k, num(0);
  std::cin >> k;
  while (k) {
    num++;
    int sum = 0;
    int tmp = num;
    while (tmp) {
      sum += tmp % 10;
      tmp /= 10;
    }
    if (sum == 10) k--;
  }
  std::cout << num;
}
void _946B() {
  long long a, b;
  std::cin >> a >> b;
  while (true) {
    if (a == 0 || b == 0) break;
    if (a >= 2 * b) {
      a %= 2 * b;
      continue;
    }
    if (b >= 2 * a) {
      b %= 2 * a;
      continue;
    }
    break;
  }
  std::cout << a << " " << b;
}
void _1108B() {
  int n, first(1), second(1), gcd(1);
  int del_first[100];
  for (int i = 0; i < 100; i++) del_first[i] = -1;
  std::cin >> n;
  int* arr = new int[n];
  for (int i = 0; i < n; i++) std::cin >> arr[i];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (arr[i] == arr[j] && i != j && arr[i] > gcd) gcd = arr[i];
  for (int i = 0; i < n; i++)
    if (arr[i] > first) first = arr[i];
  int j = 0;
  for (int i = 0; i < n; i++) {
    bool flag = false;
    if (first % arr[i] == 0) {
      int k = 0;
      while (del_first[k] != -1) {
        if (arr[i] == del_first[k]) {
          flag = true;
          break;
        }
        k++;
      }
      if (flag == true)
        continue;
      else
        del_first[j] = arr[i];
      j++;
    }
  }
  del_first[j] = first;
  for (int i = 0; i < n; i++) {
    if (first % arr[i] == 0) {
      int j = 0;
      while (del_first[j] != -1) {
        if (arr[i] == del_first[j]) {
          del_first[j] = -2;
          arr[i] = -1;
          break;
        }
        j++;
      }
    }
  }
  if (gcd == first)
    second = first;
  else
    for (int i = 0; i < n; i++)
      if (arr[i] > second) second = arr[i];
  std::cout << first << " " << second;
}
void _1051B() {
  long long l, r;
  std::cin >> l >> r;
  if (l != r) {
    std::cout << "YES" << std::endl;
    for (long long i = l; i <= r; i += 2)
      std::cout << i << " " << i + 1 << std::endl;
  } else
    std::cout << "NO";
}
void _1068B() {
  long long b;
  int counter = 0;
  std::cin >> b;
  for (long long i = 1; i * i <= b; i++) {
    if (b % i == 0) counter += 2;
    if (i * i == b) counter--;
  }
  std::cout << counter;
}
void _1076B() {
  long long n;
  long long counter = 0;
  std::cin >> n;
  if (n % 2 == 0)
    counter = n / 2;
  else {
    bool flag = false;
    for (long long i = 2; i * i <= n; i++) {
      if (n % i == 0) {
        flag = true;
        counter++;
        n -= i;
        break;
      }
    }
    if (flag == false)
      counter = 1;
    else
      counter += n / 2;
  }
  std::cout << counter;
}
void _630J() {
  long long lcm(1), n;
  std::cin >> n;
  for (long long i = 2; i <= 10; i++) lcm = lcm * i / gcd2(lcm, i);
  std::cout << n / lcm;
}
void _630K() {
  long long n, del;
  std::cin >> n;
  del = n / 2 + n / 3 + n / 5 + n / 7 - n / 6 - n / 10 - n / 14 - n / 15 -
        n / 21 - n / 35 + n / 30 + n / 42 + n / 70 + n / 105 - n / 210;
  std::cout << n - del;
}
void _1198F() {
  const int max_n = 100000;
  int arr[max_n], index[max_n], result[max_n];
  int n;
  srand(232142414);
  std::cin >> n;
  for (int i = 0; i < n; i++) {
    std::cin >> arr[i];
    index[i] = i;
  }
  for (int it = 0; it < 100; it++) {
    std::random_shuffle(index, index + n);
    int x = 0, y = 0;
    for (int i = 0; i < n; i++) {
      int t = gcd1(x, arr[index[i]]);
      if (t != x) {
        x = t;
        result[index[i]] = 1;
      } else {
        y = gcd1(y, arr[index[i]]);
        result[index[i]] = 2;
      }
    }
    if (x == 1 && y == 1) {
      std::cout << "YES" << std::endl;
      for (int i = 0; i < n; i++) std::cout << result[i] << " ";
      return;
    }
  }
  std::cout << "NO";
}
void _1295D() {
  int T;
  std::cin >> T;
  for (int i = 0; i < T; i++) {
    long long a, m;
    std::cin >> a >> m;
    long long g = gcd2(a, m);
    m /= g;
    std::cout << euler_function(m) << " ";
  }
}
void _271B() {
  int n, m, min(1000000), curr;
  int primes[9593];
  int* prime_to_go = new int[100003];
  for (int i = 0; i <= 9592; i++) primes[i] = 0;
  for (int i = 0; i <= 100003; i++) prime_to_go[i] = 1;
  int k = 0;
  for (long long i = 2; i <= 100003; i++) {
    if (prime_to_go[i] != 0) {
      primes[k] = i;
      k++;
    }
    for (long long j = i * i; j <= 100003; j += i) prime_to_go[j] = 0;
  }
  k = 0;
  for (int i = 1; i <= 100000; i++) {
    prime_to_go[i] = primes[k] - i;
    if (primes[k] - i == 0) k++;
  }
  std::cin >> n >> m;
  int** arr = new int*[n];
  for (int i = 0; i < n; i++) arr[i] = new int[m];
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) std::cin >> arr[i][j];
  for (int i = 0; i < n; i++) {
    curr = 0;
    for (int j = 0; j < m; j++) curr += prime_to_go[arr[i][j]];
    if (curr < min) min = curr;
  }
  for (int i = 0; i < m; i++) {
    curr = 0;
    for (int j = 0; j < n; j++) curr += prime_to_go[arr[j][i]];
    if (curr < min) min = curr;
  }
  std::cout << min;
}
void _230B() {
  int n;
  long long int num, j;
  std::cin >> n;
  for (int i = 0; i < n; i++) {
    std::cin >> num;
    long long sqr_num = sqrt(num);
    for (j = 2; j * j <= sqr_num; j++)
      if (num % j == 0) break;
    if (sqr_num * sqr_num == num && j * j > sqr_num && num > 1)
      std::cout << "YES" << std::endl;
    else
      std::cout << "NO" << std::endl;
  }
}
void _660A() {
  int a[1000], b[1999], n, j(0);
  std::cin >> n;
  for (int i = 0; i < n; i++) {
    std::cin >> a[i];
    if (i != 0 && gcd1(a[i], a[i - 1]) != 1) b[j++] = 1;
    b[j++] = a[i];
  }
  std::cout << j - n << '\n';
  for (int i = 0; i < j; i++) std::cout << b[i] << " ";
}
void _1360D() {
  int t;
  std::cin >> t;
  for (int i = 0; i < t; i++) {
    int n, k, result;
    std::cin >> n >> k;
    result = n;
    for (int j = 1; j * j <= n; j++) {
      if (n % j == 0) {
        if (j <= k) {
          if (result > n / j) result = n / j;
          if (n / j <= k && j <= result) result = j;
        }
      }
    }
    std::cout << result << std::endl;
  }
}
int fib(int n) {
  switch (n) {
    case 0:
      return 1;
    case 1:
      return 1;
    default:
      return fib(n - 1) + fib(n - 2);
  }
}
void _72G() {
  int n;
  std::cin >> n;
  std::cout << fib(n);
}
void _1353C() {
  int t;
  std::cin >> t;
  for (int i = 0; i < t; i++) {
    long long n, count(0);
    std::cin >> n;
    for (long long i = 1; i <= n / 2; i++) count += i * i;
    count *= 8;
    std::cout << count << std::endl;
  }
}
void _1354A() {
  int t;
  std::cin >> t;
  for (int i = 0; i < t; i++) {
    long long a, b, c, d, _time;
    std::cin >> a >> b >> c >> d;
    _time = b;
    if (_time < a) {
      if (c > d) {
        long long it_count = (a - b) / (c - d);
        if ((a - b) % (c - d) != 0) it_count++;
        _time += it_count * c;
      } else
        _time = -1;
    }
    std::cout << _time << std::endl;
  }
}
void _1358A() {
  int t;
  std::cin >> t;
  int* ans = new int[t];
  for (int i = 0; i < t; i++) {
    int n, m;
    std::cin >> n >> m;
    if (n % 2 == 0 || m % 2 == 0)
      ans[i] = n * m / 2;
    else
      ans[i] = (n / 2) * m + ((m + 1) / 2);
  }
  for (int i = 0; i < t; i++) std::cout << ans[i] << std::endl;
}
void _1364A() {
  int t;
  std::cin >> t;
  int* ans = new int[t];
  for (int i = 0; i < t; i++) {
    int n, x, l(-1), r(-1), sum(0);
    std::cin >> n >> x;
    for (int j = 0; j < n; j++) {
      int arr_j;
      std::cin >> arr_j;
      if (l == -1 && arr_j % x != 0) l = j;
      if (arr_j % x != 0) r = j;
      sum += arr_j;
    }
    if (sum % x != 0)
      ans[i] = n;
    else {
      if (l != -1) {
        if (l == r) {
          if (n - (l + 1) >= l + 1)
            ans[i] = n - (l + 1);
          else
            ans[i] = l + 1;
        } else {
          if (n - (l + 1) >= r)
            ans[i] = n - (l + 1);
          else
            ans[i] = r;
        }
      } else
        ans[i] = -1;
    }
  }
  for (int i = 0; i < t; i++) std::cout << ans[i] << std::endl;
}
void _1368A() {
  int t;
  std::cin >> t;
  int* ans = new int[t];
  for (int i = 0; i < t; i++) {
    ans[i] = 0;
    int a, b, n;
    std::cin >> a >> b >> n;
    while (a <= n && b <= n) {
      if (a >= b)
        b += a;
      else
        a += b;
      ans[i]++;
    }
  }
  for (int i = 0; i < t; i++) std::cout << ans[i] << std::endl;
}
void _1370A() {
  int t;
  std::cin >> t;
  int* ans = new int[t];
  for (int i = 0; i < t; i++) {
    int n;
    std::cin >> n;
    if (n % 2 != 0) n--;
    ans[i] = n / 2;
  }
  for (int i = 0; i < t; i++) std::cout << ans[i] << std::endl;
}
void _1367B() {
  int t;
  std::cin >> t;
  int* ans = new int[t];
  for (int i = 0; i < t; i++) {
    int n, err_count1(0), err_count2(0);
    std::cin >> n;
    int* arr = new int[n];
    for (int j = 0; j < n; j++) std::cin >> arr[j];
    for (int j = 0; j < n; j++) {
      if (j % 2 == 0 && arr[j] % 2 != 0) err_count1++;
      if (j % 2 != 0 && arr[j] % 2 == 0) err_count2++;
    }
    if (err_count1 != err_count2)
      ans[i] = -1;
    else
      ans[i] = err_count1;
    delete[] arr;
  }
  for (int i = 0; i < t; i++) std::cout << ans[i] << std::endl;
}
int main() { _1353C(); }
