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