• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

دنباله‌ی ${f_n}$ برای همه‌ی اعداد طبیعی مثل $n$ ساخته می‌شود. ابتدا مقدار $f_1 = 2$ درنظر بگیرید. برای $n$های بزرگ‌تر از ۱، مقدار $f_n$ به این صورت بدست می‌آید:

اگر $n$ عددی زوج باشد: $$f_n = \lfloor\frac{f_{n-1}}{2}\rfloor \times \lceil\frac{f_{n-1}}{2}\rceil$$

اگر $n$ عددی فرد باشد: $$f_n = f_{n-1} - 4$$

منظور از $\lfloor x \rfloor$ (بخوانید کَفِ $x$) بزرگ‌ترین عدد صحیح، کوچک‌تر یا مساوی $x$ است. برای مثال $\lfloor 3.2 \rfloor = 3$، $\lfloor -1.3 \rfloor = -2$ و $\lfloor 2 \rfloor = 2$.

منظور از $\lceil x \rceil$ (بخوانید سَقفِ $x$) کوچک‌ترین عدد صحیح، بزرگ‌تر یا مساوی $x$ است. برای مثال $\lceil 3.2 \rceil = 4$، $\lceil -1.3 \rceil = -1$ و $\lceil 2 \rceil = 2$.

حال از شما $t$ سوال پرسیده می‌شود. در هر سوال یک عدد طبیعی مثل $n$ داده می‌شود و از شما مقدار $f_n$ را می‌خواهند.

ورودی

در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده که تعداد سوالات را نشان می‌دهد.

$$1 \leq t \leq 100,000$$

در $t$ سطر بعدی، در هر سطر، یک عدد صحیح و مثبت مثل $n$ داده می‌شود.

$$1 \leq n \leq 10^9$$

خروجی

در $t$ سطر مختلف پاسخ سوالات را به ترتیب چاپ کنید.

مثال‌ها

ورودی نمونه ۱

5
1
7
2
1403
8

خروجی نمونه ۱

2
-3
1
-3
2

$f_1 = 2$

$f_2 = \lfloor\frac{f_1}{2}\rfloor \times \lceil\frac{f_1}{2}\rceil = \lfloor\frac{2}{2}\rfloor \times \lceil\frac{2}{2}\rceil = 1 \times 1 = 1$

$f_3 = f_2 - 4 = 1 - 4 = -3$

$f_4 = \lfloor\frac{f_3}{2}\rfloor \times \lceil\frac{f_3}{2}\rceil = \lfloor\frac{-3}{2}\rfloor \times \lceil\frac{-3}{2}\rceil = -2 \times -1 = 2$

$f_5 = f_4 - 4 = 2 - 4 = -2$

$f_6 = \lfloor\frac{f_5}{2}\rfloor \times \lceil\frac{f_5}{2}\rceil = \lfloor\frac{-2}{2}\rfloor \times \lceil\frac{-2}{2}\rceil = -1 \times -1 = 1$

$f_7 = f_6 - 4 = 1 - 4 = -3$

$f_8 = \lfloor\frac{f_7}{2}\rfloor \times \lceil\frac{f_7}{2}\rceil = \lfloor\frac{-3}{2}\rfloor \times \lceil\frac{-3}{2}\rceil = -2 \times -1 = 2$