This year Triwizard Championship is being organized in Hogwarts. For the final task, each of the candidates was given a magic number k. With this given number, the candidates have to answer the number of possible 3×3 magic squares that can be formed such that the magic of the square is k.

But since it’s an event at Hogwarts, their definition of Magic square is different. The features of Hogwart’s Magic Square with a magic number k are given as :

Sum of all the numbers in each row is equal to k

Sum of all the numbers in each column is equal to k

Sum of all the numbers in each diagonal is equal to k

All the numbers in the magic square are in the range of 1 to k (including both)

There should be at least 1 odd number in the Hogwart’s Magic Square

All the numbers need not be distinct.

Input:

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

Each test case consists of a single integer k.

Output:

For each test case, output a single integer, the number of magic squares possible.

Constraints

1≤T≤100

2≤k≤109

Sample Input:

3

1

3

12

Sample Output:

0

1

20