HAPLESS HEDONISM

Bob is a world-renowned stick collector. His most prized stick possessions include:

an Arctic Redwood branch from a hike near Dawson City,
a Desert Pine stick from a visit to the Grand Canyon, and
a Chinese Arbour twig from an adventure into Tibet.

Bob collects sticks in a peculiar way. He will only accept a new stick into his collection if its length is exactly length n + 1 cm where n is the number of sticks currently in his collection. This implies his collection of n sticks contains exactly one stick of length 1 cm through n cm.

One day Alice visited Bob to inspect his stick collection (upon Bob’s insistence of course). Alice wasn’t particularly interested in Bob’s excessive descriptions and needed a quick conversation changer. Cleverly, she posed the following question to Bob: “If you are allowed to take any 3 sticks from your collection, how many different triangles can you make?”

Can you help Bob answer the question so he can get back to telling Alice about his sticks?

Program Input

The input will begin with t (1 ≤ t ≤ 1000), the number of test cases. Each test case will contain an integer n (3 ≤ n ≤ 1000000), the number of sticks in Bob’s collection. (Recall if Bob has n sticks, then he has exactly one stick of each of the lengths from 1 cm through n cm.)

Program Output

For each test case, output on a line the number of different triangles you can make with Bob’s sticks. Triangles X and Y are different if there is at least one stick in X that is not in Y. A triangle has area strictly greater than 0.

Sample Input & Output

INPUT

OUTPUT

0
1
50

Calgary Collegiate Programming Contest 2008