Fabby is the princess of byteland. She is a genius and loves to play with triangles. One day, while playing with triangles in a moonlit night, she saw a shadow. The shadow came and whispered a song about the beauty of triangles. She loved the song and was curious about him.
She asked, "Who are you?"
He replied, "Ghost."
"Ghost? which kind of ghost are you?"
"A ghost who possesses computers and orders them to do tasks and kills bugs."
"Impressive! Okay ghost, can you possess my computer to calculate the number of Fabbyfied triangles?"
"For you? Yes, I can. In return what will I get?"
"You will get Fabbyfied too!"
That moonlit night ghost wrote a program to calculate the number of Fabbyfied Triangles for a given value n and got Fabbyfied.
Definition of Fabbyfied triangle for a number n: A triangle will be called Fabbyfied for a value n if there is exactly one side of length n and other two has length x, y such that 1 < x < y < n. Two triangles will be called different if at least one side is different in length. All lengths are integer.
You are Ghost's juniors. Now you have to answer Q queries. In each query, you will be given n and you have to find out what Ghost's program returned for the value of n.
Input
Input starts with an integer Q. Q denotes the number queries.
Each of the Q lines will contain only one integer n.
1 ≤ Q ≤ 106
1 ≤ n ≤ 109
Output
For each case output a single integer, the answer for the queries in each line.
Sample
| Input | Output |
|---|---|
3 8 10 20 | 9 16 81 |
The area of a triangle must be positive.
