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

---

شاگردان استاد که با شماره‌های \(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\) نشان‌دهنده‌ی یای انحصاری است.

ورودی

در خط اول ورودی عدد صحیح \(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\]