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
import java.util.*;
import javax.naming.directory.InvalidAttributesException;
import java.io.InputStreamReader;
import java.io.Writer;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.lang.Math;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.PrintWriter;

public class one {

   static boolean isPalindrome(String word) {
    word = word.toLowerCase();
    int start = 0;
    int end = word.length() - 1;
    boolean flag = true;
    while (start <= end) {
      if (word.charAt(start) != word.charAt(end)) {
        flag = false;
        break;
      } else
        start++;
      end--;
    }
    return flag;
  }

  static boolean isVowel(char x) {
    if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O'
        || x == 'U')
      return true;
    else
      return false;
  }

   static boolean isPrime(int n) {

    if (n <= 1)
      return false;
    if (n <= 3)
      return true;

    if (n % 2 == 0 || n % 3 == 0)
      return false;

    for (int i = 5; i * i <= n; i = i + 6)
      if (n % i == 0 || n % (i + 2) == 0)
        return false;

    return true;
  }

  static boolean isPerfectSquare(double x) {
    double sr = Math.sqrt(x);
    return ((sr - Math.floor(sr)) == 0);
  }

  static int gcd(int a, int b) {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }

  static long gcd(long a, long b) {
    if (b == 0)
      return a;
    return gcd(b, a % b);
  }

  static long lcm(long a, long b) {
    return (a * b) / gcd(a, b);
  }

  static class FastReader {
    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
      br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine() throws IOException, InvalidAttributesException {
      String str = "";
      str = br.readLine();
      return str;
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; ++i)
        array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; ++i)
        array[i] = nextLong();
      return array;
    }

    public ArrayList<Integer> nextIntArrayList(int n) {
      ArrayList<Integer> ar = new ArrayList<>();
      for (int i = 0; i < n; i++)
        ar.add(nextInt());
      return ar;
    }

    public ArrayList<Long> nextLongArrayList(int n) {
      ArrayList<Long> ar = new ArrayList<>();
      for (int i = 0; i < n; i++)
        ar.add(nextLong());
      return ar;
    }

    public int[][] nextIntMatrix(int n, int m) {
      int[][] matrix = new int[n][m];
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
          matrix[i][j] = nextInt();
      return matrix;
    }

    public long[][] nextLongMatrix(int n, int m) {
      long[][] matrix = new long[n][m];
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
          matrix[i][j] = nextLong();
      return matrix;
    }

    public char[][] nextCharMatrix(int n, int m) {
      char[][] matrix = new char[n][m];
      for (int i = 0; i < n; ++i)
        matrix[i] = next().toCharArray();
      return matrix;
    }

  }

  static class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
      writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
      this.writer = new PrintWriter(writer);
    }


    public void print(Object... objects) {
      for (int i = 0; i < objects.length; i++) {
        if (i != 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void print(int[] array) {
      for (int i = 0; i < array.length; i++) {
        if (i != 0) {
          writer.print(' ');
        }
        writer.print(array[i]);
      }
    }

    public void print(double[] array) {
      for (int i = 0; i < array.length; i++) {
        if (i != 0) {
          writer.print(' ');
        }
        writer.print(array[i]);
      }
    }

    public void print(long[] array) {
      for (int i = 0; i < array.length; i++) {
        if (i != 0) {
          writer.print(' ');
        }
        writer.print(array[i]);
      }
    }

    public void print(char[] array) {
      for (int i = 0; i < array.length; i++) {
        if (i != 0) {
          writer.print(' ');
        }
        writer.print(array[i]);
      }
    }

    public void print(String[] array) {
      for (int i = 0; i < array.length; i++) {
        if (i != 0) {
          writer.print(' ');
        }
        writer.print(array[i]);
      }
    }

    public void print(int[][] matrix) {
      for (int i = 0; i < matrix.length; ++i) {
        println(matrix[i]);
      }
    }

    public void print(double[][] matrix) {
      for (int i = 0; i < matrix.length; ++i) {
        println(matrix[i]);
      }
    }

    public void print(long[][] matrix) {
      for (int i = 0; i < matrix.length; ++i) {
        println(matrix[i]);
      }
    }

    public void print(char[][] matrix) {
      for (int i = 0; i < matrix.length; ++i) {
        println(matrix[i]);
      }
    }

    public void print(String[][] matrix) {
      for (int i = 0; i < matrix.length; ++i) {
        println(matrix[i]);
      }
    }

    public void println(int[] array) {
      print(array);
      writer.println();
    }

    public void println(double[] array) {
      print(array);
      writer.println();
    }

    public void println(long[] array) {
      print(array);
      writer.println();
    }

    // public void println(char[] array) {
    // print(array);
    // writer.println();
    // }

    public void println(String[] array) {
      print(array);
      writer.println();
    }

    public void println() {
      writer.println();
    }

    public void println(Object... objects) {
      print(objects);
      writer.println();
    }

    public void print(char i) {
      writer.print(i);
    }

    public void println(char i) {
      writer.println(i);
    }

    public void println(char[] array) {
      writer.println(array);
    }

    public void printf(String format, Object... objects) {
      writer.printf(format, objects);
    }

    public void close() {
      writer.close();
    }

    public void flush() {
      writer.flush();
    }

    public void print(long i) {
      writer.print(i);
    }

    public void println(long i) {
      writer.println(i);
    }

    public void print(int i) {
      writer.print(i);
    }

    public void println(int i) {
      writer.println(i);
    }

    public void separateLines(int[] array) {
      for (int i : array) {
        println(i);
      }
    }
  }

  public static void main(String[] args) {
    FastReader sc = new FastReader();
    OutputStream outputStream = System.out;
    OutputWriter out = new OutputWriter(outputStream);

    int t = sc.nextInt();

    while (t-- > 0) {
      int n = sc.nextInt();
      int sum=0;
      sum=n*(n+1)*(n-1)/24;
      sum=sum*8;
      out.println(sum);

    }
    out.flush();
    out.close();

  }
}
