+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آرمین و پارسا عید خود را با بازی مثلثایره‌ گذراندند. در این بازی $n$ ردیف داریم که در ردیف $i$ام، $i$ تا دایره وجود دارد و این دایره‌ها مانند شکل زیر روی همدیگر قرار گرفته‌اند.  حال بازی به این صورت انجام می‌شود که ابتدا پارسا در هر ردیف دقیقا یک دایره را قرمز می‌کند و سپس آرمین از بالاترین دایره شروع می‌کند و هر دفعه از دایره‌ای که روی آن هست به دایره‌ای می‌رود که دقیقا زیر دایره فعلی هست (دو دایره این خصوصیت را دارند یعنی یا پایین چپ می‌رود یا پایین راست). این کار را تا وقتی انجام می‌دهد که به یک دایره‌ای از ردیف $n$ برسد. امتیاز آرمین برابر با تعداد دایره‌های قرمزی است که از روی آن رد می‌شود. حال پارسا می‌خواهد امتیاز آرمین کمینه شود و آرمین می‌خواهد امتیاز خود را بیشینه کند. اگر هر دو به بهترین شکل بازی کنند امتیاز پایانی آرمین چند می‌شود؟ # ورودی این مسئله $T$ تا تست کیس دارد. $$1 \le T \le 10^{5}$$ در هر تست کیس عدد $n$ ورودی داده می‌شود. $$1 \le n \le 10^{18}$$ # خروجی به ازای هر تست کیس در خط‌های جدا امتیاز پایانی آرمین در صورتی که هر دو به بهترین شکل بازی کنند را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 3 ``` ## خروجی نمونه ۱ ``` 1 2 2 ```