Migrated from Lutece 394 Tunnel

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

As is known to all, there was a huge earthquake attacking Japan recently, thus leading a series of after-disasters, suchas Tsunami, swollowing a vast piece of land.Countless people died while many others lost their home.

L.Alexander and Jinjin were one couple of lover of the homeless in the Tsunami. hand in hand, they were washed away by the high tide. After a long period of drifting, they landed at a place called Libya. Faced with a brand-new surroundings this couple decided to rebuild their home. But life is full of frustration, the leader of Libya, Omar Mouammer al Gaddafi,offenced some leaders of powerfulcountries, resulting in Libya's being bombed by the airfoce of the Country Combination. So there was a trail of destruction in the poor country after being bombed,however love is strong and love is full of magic power,which makes the couple determined to go against all obstacles that against their reconstruction, despite the war adding difficulties.

They learn from the great Chinese people defending the Japanese 60 years ago, and lead the peole there to dig tunnels to fight againt their enemies. They dig tunnels between the beacheads and Gaddafi. To save labor and time, assume there is a tunnel between $A$ and $B$, also between $B$ and $C$, and there will be no tunnel between $A$ and $C$. That is, there does not exist three places such that every pair of them are connected by a tunnel.

In this case your task is to figure out a way to dig as many tunnels as possible to help Omar Mouammer al Gaddafi, striving for the independece. Give out your plan!

Input

The first line is an integer $T$ which stands for the number of test cases.

Each test case contain one line with an integer $N$ ($0\leq N\leq 10000$) indicating the number of places.

Output

For each test case only one line with an integer indicating the number of tunnels that can be dug.

Samples

2
1
6

0
9

Resources

10th SCU Programming Contest Final