"Welcome today, champions. Now you've waited, you've wondered, and finally, the moment has arrived. A moment only four of you can fully appreciate." - Albus Dumbledore

Albus Dumbledore announces that Hogwarts will host the Triwizard Tournament where three magical schools will test their might, in three daunting challenges. The champions taking part, as selected by the Goblet of Fire are, Cedric Diggory of Hufflepuff representing Hogwarts, Viktor Krum representing Durmstrang Institute, and Fleur Delacour for the Beauxbatons Academy of Magic.

The Goblet unexpectedly chose a fourth champion: Chotu.

As the tournament's first task, the champions must each retrieve a golden egg guarded by a dragon. After the successfull retrieval of golden eggs by the three contestants, now it's Chotu's turn. As he is quite nervous, his friend Hermione told him that if he casts a spell of size N, he can beat the dragon.
In the world of wizards, a spell comprises of three magical letters 'I', 'L', 'U'. A spell is of the form I^p L^q U^r. A spell of size N is valid if p + q + r = N and p, q, r > 0.
For example - For N = 6 "IIILUU" is a valid spell, whereas "UUULLL" is not a valid spell.

Now Chotu is wondering how many different spells can he cast to defeat the dragon. A spell is different from another spell, if atleast one of p, q, r is different.

Input
First line contains an integer T denoting number of test cases.
Next T lines contains an integer N.

Output
For each test case output the number of spells.

Constraints
1 <= T <= 100.
3 <= N <= 10⁵