Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fabbyfied Triangle

By Hasinur_ · Limits 1s, 512 MB

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.
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

InputOutput
3
8
10
20
9
16
81


The area of a triangle must be positive.

Statistics

71% Solution Ratio

RUET_SDZEarliest, Nov '18

rifatrraazzFastest, 0.1s

skmonirLightest, 10 MB

mdvirusShortest, 230B