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

---

ما یک رشته‌ی $m$ بیتی داریم (یعنی تمام کاراکترهای آن 0 و 1 هستند) به صورت $a_1, a_2, \dots, a_m,$ و این رشته را با استفاده از کدگذاری همینگ ($Hamming ,Code$) کدگذاری کرده‌ایم.

ایده‌ی کلی این روش افزودن تعدادی بیت اضافه به رشته است. این بیت‌ها طبق قواعد خاصی محاسبه می‌شوند و به آن‌ها بیت‌های توازن یا $parity$ گفته می‌شود. این بیت‌ها به ما کمک می‌کنند تا بررسی کنیم که آیا رشته دچار خطا شده است یا خیر.

یکی از کاربردهای کدگذاری همینگ این است که در فرآیند انتقال داده، اگر حداکثر یک بیت تغییر کند، می‌توان با استفاده از این کدگذاری خطا را شناسایی و در صورت امکان اصلاح کرد.

در روش کدگذاری همینگ، اگر $m$ تعداد بیت‌های رشته‌ی اصلی و $r$ تعداد بیت‌های توازن باشد، شرط زیر باید برقرار باشد: $$ 2^r \geq m + r + 1 $$

برای محاسبه‌ی $r$، کوچک‌ترین عدد طبیعی را انتخاب می‌کنیم که این رابطه را ارضا کند.
برای مثال، اگر $m = 11$ باشد، مقدار $r = 4$ خواهد بود.

سپس رشته‌ی جدیدی به طول $n = m + r$ (شامل بیت‌های اصلی و بیت‌های توازن) به صورت $b_1, b_2, \dots, b_{n}$ می‌سازیم. بیت‌های توانی از ۲ ($1, 2, 4, 8, \dots$) برای بیت‌های توازن رزرو می‌شوند و باقی بیت‌ها به ترتیب از رشته‌ی اصلی پر می‌شوند.

برای مثال، اگر $m = 11$ و رشته‌ی اصلی برابر 01010111010 باشد، رشته‌ی جدید به صورت ??0?101?0111010 ساخته می‌شود.

در مرحله‌ی بعد، مقدار هر بیت توازن $b_{2^i}$ ($i$ از $0$ تا $r-1$) را به صورت یای‌انحصاری ($XOR$) بیت‌هایی از رشته‌ی $b$ که در موقعیت‌های باینری آن‌ها بیت $i$ برابر ۱ است، محاسبه می‌کنیم.

یک رشته‌ی $n$ بیتی به ما داده شده که طبق کدگذاری همینگ ساخته شده است. از شما خواسته می‌شود که بررسی کنید آیا رشته دارای خطا است یا خیر و اگر رشته دقیقاً یک خطا دارد، موقعیت خطا را شناسایی و رشته را اصلاح کنید و اگر رشته معتبر نباشد (مثلاً بیش از یک خطا داشته باشد)، INVALID چاپ کنید.

ورودی

در خط سطر اول ورودی، عدد صحیح $t$ آمده که تعداد تست‌ها را نشان می‌دهد.

$$ 1 \leq t \leq 1000$$

در سطر اول هر تست، یک عدد صحیح $n$ آمده که طول رشته‌ی باینری کدگذاری شده را نشان می‌دهد. $$ 2 \leq n \leq 100,000 $$

در سطر دوم هر تست، یک رشته‌ی باینری $n$ بیتی شامل کاراکترهای 0 و 1 داده می‌شود که کاراکترهای رشته‌ی کدگذاری شده را به‌ترتیب نشان می‌دهد.

تضمین می‌شود مجموع مقادیر $n$ در تمام تست‌کیس‌ها از $1,000,000$ بیشتر نخواهد شد.

خروجی

برای هر تست، در سطر اول، YES، اگر رشته دارای خطاست، NO، اگر رشته بدون خطاست و INVALID، اگر رشته نامعتبر است. همچنین اگر رشته خطا داشت و اصلاح شد، در خط دوم رشته‌ی اصلاح‌شده را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

3
4
1010
11
10101001110
8
00000000

خروجی نمونه ۱

YES
1110
INVALID
NO