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
// package name;
import java.io.*;
import java.util.*;

public class Main {
	static final long mod = 1000000007;
	static final long lmx = 9223372036854775807l, lmn = -9223372036854775808l;
	static final int imx = 2147483647, imn = -2147483648;
	static final String Y = "YES", NO = "NO", LN = "\n", SPC = " ";
	static Scanner s = new Scanner(System.in);
	//static Reader s = new Reader();
	static PrintWriter out = new PrintWriter(System.out);

	public static void main(String[] args) throws IOException {
		int t = 1;
		t = s.nextInt();
		String xy = slinp();
		StringBuffer sb = new StringBuffer();
		while (t > 0) {
			t--;
			int n = iinp();//, k = iinp();
			long sum = 0, z = 8;
			for(int i = 1; i <= n / 2; i++) {
				sum += z * i;
				z += 8;
			}
			sb.append(sum);
			/*long n = linp(), m = linp();
			if(n == 1) sb.append(0);
			else if(n == 2) sb.append(m);
			else {
				long x = n / 2;
				long ans = 0;
				long one = m / x;
				long r = m % x;
				ans += 2 * r * (one + 1);
				ans += 2 * (x - r) * one;
				if(n % 2 == 0) ans -= 2 * r * one;
				sb.append(ans);
			}*/
			sb.append(LN);
		}
		out.print(sb);
		out.flush();
	}

	static int iinp() throws IOException {
		return s.nextInt();
	}

	static long linp() throws IOException {
		return s.nextLong();
	}

	static double dinp() throws IOException {
		return s.nextDouble();
	}

	static String sinp() throws IOException {
		return s.next();
	}

	static String slinp() throws IOException {
		return s.nextLine();
	}

	static int[] iarr(int n) {
		return new int[n];
	}

	static long[] larr(int n) {
		return new long[n];
	}

	static double[] darr(int n) {
		return new double[n];
	}

	static boolean[] barr(int n) {
		return new boolean[n];
	}

	static String[] sarr(int n) {
		return new String[n];
	}

	static int[][] iarr(int n, int m) {
		return new int[n][m];
	}

	static long[][] larr(int n, int m) {
		return new long[n][m];
	}

	static int[] iinp(int n, int st, int size) throws IOException {
		int a[] = iarr(n);
		for (int i = st; i < st + size; i++)
			a[i] = iinp();
		return a;
	}

	static long[] linp(int n, int st, int size) throws IOException {
		long a[] = larr(n);
		for (int i = st; i < st + size; i++)
			a[i] = linp();
		return a;
	}

	static String[] sinp(int n, int st, int size, String str) throws IOException {
		String a[] = sarr(n);
		for (int i = st; i < st + size; i++)
			if (str.equalsIgnoreCase(SPC))
				a[i] = sinp();
			else
				a[i] = slinp();
		return a;
	}

	static int[][] iinp(int n, int m, int row, int rows, int col, int cols) throws IOException {
		int a[][] = iarr(n, m);
		for (int i = row; i < row + rows; i++)
			for (int j = col; j < col + cols; j++)
				a[i][j] = iinp();
		return a;
	}

	static long[][] linp(int n, int m, int row, int rows, int col, int cols) throws IOException {
		long a[][] = larr(n, m);
		for (int i = row; i < row + rows; i++)
			for (int j = col; j < col + cols; j++)
				a[i][j] = linp();
		return a;
	}

	static void ginp(ArrayList<Integer> g[], int m) throws IOException {
		for (int i = 0; i < m; i++) {
			int u = iinp(), v = iinp();
			g[u].add(u);
			g[v].add(u);
		}
	}

	static long min(long... a) {
		long min = lmx;//Long.MAX_VALUE;
		for (long i : a)
			if (i < min)
				min = i;
		return min;
	}

	static int min(int... a) {
		int min = imx;//Long.MAX_VALUE;
		for (int i : a)
			if (i < min)
				min = i;
		return min;
	}

	static long max(long... a) {
		long max = lmn;//Long.MIN_VALUE;
		for (long i : a)
			if (i > max)
				max = i;
		return max;
	}

	static int max(int... a) {
		int max = imn;//Long.MIN_VALUE;
		for (int i : a)
			if (i > max)
				max = i;
		return max;
	}

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

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

	static void sort(int a[]) {
		Arrays.sort(a);
	};

	static void sort(long a[]) {
		Arrays.sort(a);
	};

	static void sort(String a[]) {
		Arrays.sort(a);
	};

	static void sort(int a[], int st, int e) {
		Arrays.sort(a, st, e);
	};

	static void sort(long a[], int st, int e) {
		Arrays.sort(a, st, e);
	};

	static void sort(String a[], int st, int e) {
		Arrays.sort(a, st, e);
	};

	static void sortbycol(int arr[][]) {
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] x, int[] y) {
				if (x[1] == y[1])
					return x[2] - y[2];
				return x[1] - y[1]; // sort in increasing order on the basis of first column
			}
		});
	}

	static StringBuffer printarr(long a[], String str) {
		StringBuffer ans = new StringBuffer();
		for (long i : a)
			ans.append(i + str);
		return ans;
	}

}

class Pair implements Comparator<Pair> {
	long a, b;

	Pair(long x, long y) {
		a = x;
		b = y;
	}

	public int compare(Pair p1, Pair p2) {
		if (p1.a != p2.a)
			return (p1.a - p2.a > 0) ? 1 : -1;
		return (p1.b - p2.b > 0) ? 1 : -1;
	}
}
