Misha used all the bumps for planting new trees in the forest and had to play with Masha, there were only twigs. It is natural that during the winter they dried up, and as more and were neatly stacked, then another, and all lined. Once Masha restore order in the house, they discovered neatly stacked branches, longer similar to sticks, and gleefully ran to Misha: - \textit{Hey, Misha! I found our toys - let's play!} Since Bear was on his walk, he blurted out the first thing that he got it into my head: - \textit{You first tell me, Mary, how many different triangles can you construct from these branches?} - and seeing the surprised eyes of Masha, a sly further snarled - \textit{but then I got tired already to help you with the math ... Oh, and do not forgetthat you can use every time, only 3 out of found you.} - finally puzzled little girl old bear. Satisfied Mischa quickly went into the woods for a walk, but Mary thought for a long time. The first thing she measured the length of all branches and with still greater astonishment found that they all have different lengths, while the smallest has a length of \textbf{1} cm. After trying to sort in ascending branches of length she found another pattern: each sleduyaschaya twig and exactly \textbf{1} cm longer than the previous one. - \textit{Yes, something is definitely wrong} - thought Masha and already well-learned all the tricks of the wise bear, began to experiment in constructing triangles. Masha help solve this puzzle for the return of Misha. \InputFile The first line of each test contains a number of test cases \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{1000}). In each of the following \textbf{T} lines have one single number - the number of detected Masha sprigs \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{1000000}). \OutputFile For each test case in a separate line output a single number - the answer to the problem.