+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شاگردان استاد که با شماره‌های $0$ تا $n-1$ شماره‌گذاری شده‌اند، به ترتیب در یک ردیف نشسته‌اند. استاد که از سر و صدای شاگردانش کلافه شده، قصد دارد تا ترتیب نشستن آن‌ها را تغییر دهد. برای تغییر جای شاگردان، استاد عددی مانند $x$ که $0 \le x \le n-1$ انتخاب می‌کند و سپس برای هر شاگرد مانند $i$ ($0 \le i \le n-1$) او را به جای‌گاه $i \oplus x$ می‌فرستد. استاد عدد صحیح $x$ را خوب می‌نامد اگر پس از اعمال جابه‌جایی با این عدد، هر شاگرد در یکی از جای‌گاه‌های $0$ تا $n-1$ باقی بماند. به بیان دیگر، عدد $x$ ($0 \le x \le n-1$) خوب است اگر برای هر $i$ که $0 \le i \le n-1$ داشته باشیم $0 \le i \oplus x \le n-1$. به استاد کمک کنید و تعداد اعداد خوب را برای او بشمارید. در این‌جا $\oplus$ نشان‌دهنده‌ی [یای انحصاری](https://fa.wikipedia.org/wiki/%DB%8C%D8%A7%DB%8C_%D8%A7%D9%86%D8%AD%D8%B5%D8%A7%D8%B1%DB%8C) است. # ورودی در خط اول ورودی عدد صحیح $t$ ($1 \le t \le 10^5$) که برابر تعداد سناریوها است، می‌آید. در تنها خط هر سناریو، عدد صحیح $n$ ($1 \le n \le 10^{18}$) می‌آید. # خروجی برای هر سناریو، تنها یک خط شامل پاسخ مسئله در آن سناریو را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 1 2 3 ``` ## خروجی نمونه ۱ ``` 1 2 1 ``` در هر سه سناریو، $0$ عددی خوب است. در سناریوی دوم که $n = 2$، $1$ نیز عددی خوب است چرا که: $$0 \oplus 1 = 1$$ $$1 \oplus 1 = 0$$

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