SP31099 ADAROBOT - Ada and CAPTCHA

Ada the Ladybug just got an inovative idea (which might be a rival of captcha): She made following function - **F(a)=least significant 1-bit of a** (indexed from 1). She also made following recursive function **T(N)=F(N\*(N-1)) $ ^{3} $ +T(N-2)**, where **T(0)=0,T(1)=0**. Her idea is following- Instead of asking for captcha, she uses an opposite method: She gives you even **N** and you have to answer **T(N)** - if your answer is correct, then you are definetly robot and you won't be let in. As her good friend she asked you to program a checker for her.

The input begins with an integer **1 , number of queries.** The next **Q** lines contains an even integer: **2**

For each query, print **T(N)**