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

---

یک دنباله از اعداد طبیعی مثل \(a_1, a_2, \dots, a_n\,\) روی یک ردیف نوشته شده است. تخته را به دو دوست به نام‌های کدکاپ و دانابینا نشان می‌دهیم. از آن‌جایی که آن‌ها دوستان صمیمی هستند، می‌خواهند راجع به اعداد دنباله با یک‌دیگر صحبت کنند اما دانابینا نمی‌تواند اعداد را ببیند. هم‌چنین کدکاپ فقط می‌تواند به طور غیرمستقیم اعداد دنباله را به او بگوید.

کدکاپ در ابتدا تعداد اعداد دنباله یعنی \(n\) را اعلام می‌کند. سپس از اولین عضو دنباله شروع کرده و به ترتیب برای هر دو عضو متوالی از دنباله، \(\text{XOR}\) آن‌ها را محاسبه کرده و اعلام می‌کند. به عبارت دیگر \(n - 1\) عدد \(x_1, x_2, \dots, x_{n-1}\,\) که \(x_i = a_i \oplus a_{i+1}\,\) است را اعلام می‌کند.

با این‌که کدکاپ اطلاعات زیادی راجع به اعضای دنباله داده است، برای به‌دست آوردن تک‌تک اعداد دنباله کافی نیست. پس کدکاپ به دانابینا اجازه داده است که دو سوال راجع به دنباله بپرسد.

در هریک از دو سوال دانابینا باید یک مجموعه از اعضای دنباله (نه لزوماً متوالی) را مشخص کند و کدکاپ، \(\text{AND}\) آن‌ها را محاسبه کرده و اعلام می‌کند. سپس دانابینا با توجه به پاسخ کدکاپ، اعداد دنباله را به‌دست می‌آورد. امتیاز نهایی برابر است با تعداد عضو کم‌تر بین دو مجموعه‌ای که دانابینا در این دو سوال انتخاب کرده است.

بیش‌ترین امتیازی که دانابینا می‌تواند بگیرد چیست؟ دقت کنید باید \(\text{AND}\) اعضای دو مجموعه‌ای که دانابینا از اعضای دنباله انتخاب می‌کند، اطلاعات کافی برای به‌دست آوردن اعداد دنباله را به او بدهد.

ورودی

در سطر اول ورودی عدد طبیعی \(t\)، تعداد سناریوها داده می‌شود. \[1 \leq t \leq 500\]

هر سناریو در دو سطر به شما ورودی داده می‌شود. در سطر اول عدد طبیعی \(n\) به شما داده می‌شود. \[1 \leq n \leq 300\, 000\]

سپس در سطر دوم \(n-1\) عدد صحیح \(x_1, x_2, \dots, x_{n-1}\,\) به شما داده می‌شود. \[ 0 \leq x_i \leq 1000\]

تضمین می‌شود که \(1 \leq \sum n \leq 300\, 000\).

خروجی

در یک سطر، عدد طبیعی \(s\)، یعنی بیش‌ترین امتیازی که دانابینا با پرسیدن دو مجموعه و تشخیص دقیق دنباله می‌‌تواند بگیرد را خروجی دهید.

مثال‌ها

ورودی نمونه ۱

3
3
1 3
3
2 3
3
2 1

خروجی نمونه ۱

2
2
2