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

شاگردان استاد که با شماره‌های $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$$