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

public class Sol {
	public static StringBuffer sb = new StringBuffer();
	public static long mod = 1000000007;
	public static int t;
	public static Set<Integer> set = new HashSet<>();
	public static Map<String,Long> map = new HashMap<>();
	private static long pow(long a, long b, long mod) {
		long ans = 1;
		while (b > 0) {
			if (b % 2 == 1) {
				ans = (ans * a) % mod;
			}
			a = (a * a) % mod;
			b = b >> 1;
		}
		return ans;
	}

	private static long lcm(long l, long m) {
		long gcd = Gcd(l, m);
		return (l * m) / gcd;
	}

	private static long Gcd(long a, long b) {
		if (b == 0)
			return a;
		else
			return Gcd(b, a % b);
	}

	private static int Gcd(int a, int b) {
		if (b == 0)
			return a;
		else
			return Gcd(b, a % b);
	}

	private static void solve1() throws IOException {
		int max = 100001,fac=5,div=1;
		long arr[] = new long[max];
		long a = 1,b=2,c=3,d=4;

		for(int i=1;i<max;i++){
			long x  = (a*b)%mod;
			long y  = (c*d)%mod;
			x=(x*y)%mod;
			arr[i] = x;
			a++;
			b++;
			c++;
			d++;
		}
		for(int i=2;i<max;i++){
			arr[i] = (arr[i]%mod+arr[i-1]%mod)%mod;
		}

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			String str[] = br.readLine().split(" ");
			int n = Integer.parseInt(str[0]);
			int k = Integer.parseInt(str[1]);
			sb.append((arr[k]-arr[n-1]+2*mod)%mod+"\n");
		}
		System.out.println(sb);
	}

	private static void solve3() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		long arr[] = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::valueOf).toArray();
		long gcd = arr[0];
		long max = arr[0];

		for (int i = 1; i < t; i++) {
			gcd = Gcd(gcd, arr[i]);
			max = Math.max(max, arr[i]);
		}
		System.out.println(max / gcd);
	}

	private static void solve2() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			int arr[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
			int brr[] = new int[3];
			brr[0] = arr[0];
			brr[1] = arr[1];
			brr[2] = arr[2];
			Arrays.sort(brr);
			for (int i = 3; i < n; i++) {
				brr[1] = arr[i];
				Arrays.sort(brr);
			}
			for (int i = 0; i < n; i++) {
				if (arr[i] == brr[0]) {
					System.out.println(brr[0] + " " + brr[2]);
					break;
				}
				if (arr[i] == brr[2]) {
					System.out.println(brr[2] + " " + brr[0]);
					break;
				}

			}

		}
	}

	private static void solve4() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long arr[] = new long[250001];
		long pow=8;
		for(int i=1;i<250001;i++){
			arr[i] = arr[i-1]+i*pow;
			pow=pow+8;
			//System.out.println(arr[i]);
			
		}
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			long n = Long.parseLong(br.readLine());
			sb.append(arr[(int)n/2]+"\n");
		}
		System.out.println(sb);
	}

	private static void solve5() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			String str[] = br.readLine().split(" ");
			int n = Integer.parseInt(str[0]);
			int k =Integer.parseInt(str[1]);
			int arr[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
			Arrays.sort(arr);
			int total=0,i=0;
			while(k>0){
				k=k-arr[i++];
				total++;
			}
			if(k<0){
				total--;
			}
			sb.append(total+"\n");
		}
		System.out.println(sb);
	}

private static void solve6() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			String str[] = br.readLine().split(" ");
			int n = Integer.parseInt(str[0]);
			int k =Integer.parseInt(str[1]);
			long arr[] = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::valueOf).toArray();
			int query[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
			long sum=arr[0];
			for(int i=1;i<n;i++){
				sum=sum^arr[i];
			}
			long brr[] = new long[n];
			brr[0] = sum;
			for(int i=1;i<n;i++){
				brr[i] = brr[i-1]^arr[i-1];
			}
			for(int i=0;i<k;i++){
				set.add(query[i]);
			}
			long max=-1;
			long count=0;
			for(int i=0;i<n;i++){
				if(set.contains(i+1)){
					max=Math.max(max,brr[i]);
				}
				if(brr[i]<max){
					count+=arr[i];
				}
			}
			sb.append(count+"\n");
		}
		System.out.println(sb);
	}
	private static long check(long n) {
		if (n == 1) {
			return 0;
		}
		long k = n/2;
		long sum=0;
		long pow=8;
		for(int i=1;i<=k;i++){
			sum+=i;
		}
		return 0;

		
	}

	public static void main(String[] args) throws IOException {
		 //solve1(); // input in the form of 
					 // 3
					 // 1 5
					 // 5 7
					 // 8 9
		// solve2(); // input in the form
					// 2
					// 3
					// 1 2 3
					// 2
					// 1 2
		// solve3();
		 solve4();

		//solve5();
		//solve6();
		//solve();

	}

	private static void solve() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int t = Integer.parseInt(br.readLine());
		while (t-- > 0) {
			String s[] = br.readLine().split(" ");
			int n =Integer.parseInt(s[0]);
			int k =Integer.parseInt(s[1]);
			int arr[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
			int brr[] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
			Arrays.sort(arr);
			Arrays.sort(brr);
			int sum=0;
			int mu = n-1,b=0;

			for(int i=0;i<n;i++){
				if(arr[i]<brr[mu] && b<k){
					sum+=brr[mu];
					mu--;
					b++;
				}else{
					break;
				}
			}
			for(int i=b;i<n;i++){
				sum+=arr[i];
			}
			sb.append(sum+"\n");


			
		
		}System.out.println(sb);

	}
}
