+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ----------  دنباله‌ی $\{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$

حل سؤال در بانک سؤالات