- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در زبان برنامه‌نویسی گولنگستان متغیرها حافظه‌های ۱، ۲، ۳ یا ۴ بایتی دارند. وقتی یک شئ با $n$ متغیر به حجم‌های $s_1, s_2, \dots, s_n,$ تعریف می‌کنیم. حافظه‌ها با قاعده‌ی زیر در بسته‌های ۴ بایتی، پشت سرهم قرار می‌گیرند.
متغیرها را به ترتیب اضافه می‌کنیم. اگر متغیری که نوبت اضافه شدن آن است، به انتهای بسته‌ی قبلی می‌تواند اضافه شود، آن را اضافه می‌کنیم و به سراغ متغیر بعدی (در صورت وجود) می‌رویم. اما اگر این متغیر نمی‌تواند به انتهای بسته‌ی آخر اضافه شود، همه‌ی فضای خالی آن را رها می‌کنیم و آن بسته را می‌بندیم (اصطلاحاً به این حافظه‌های تلف شده padding space می‌گویند). سپس در یک بسته‌ی ۴ بایتی جدید، حافظه مورد نیاز متغیر بعدی را به بایت‌های اول آن اختصاص می‌دهیم.
برای مثال فرض کنید $n = 3$ متغیر داشته باشیم: $s_1 = 1$، $s_2 = 4$ و $s_3 = 1$. در این صورت متغیر $s_1$ در ابتدای یک بسته قرار می‌گیرد، چون متغیر $s_2$ را نمی‌توان به همان بسته اضافه کرد، پس ۳ بایت باقی‌مانده‌ی بسته‌ی اول را padding space در نظر می‌گیریم. سپس متغیر $s_2$ را در یک بسته‌ی جدید قرار داده و در نهایت $s_3$ را در بایت اول یک بسته قرار می‌دهیم. (در آخرین بسته padding space نداریم.)
به این ترتیب وضعیت نوار حافظه به صورت زیر خواهد بود و در مجموع ۳ حافظه تلف شده خواهیم داشت.
حال می‌دانیم اگر ترتیب این سه متغیر را به این صورت که $s_1 = 4$، $s_2 = 1$ و $s_3 = 1$ عوض می‌کردیم. وضعیت نوار حافظه به این صورت تغییر می‌کرد و هیچ حافظه‌ای تلف نمی‌شود.
حال به شما ترتیب اولیه حافظه متغیرها داده می‌شود از شما می‌خواهیم ترتیب آن‌ها را طوری تغییر دهید که حافظه‌های تلف شده (padding space) کمینه شود و در نهایت این کمینه مقدار را چاپ کنید.
ورودی
در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده که تعداد سناریوها را نشان می‌دهد.
$$1 \leq t \leq 1000$$
در سطر اول هر سناریو، عدد صحیح $n$ که نشان دهنده‌ی تعداد متغیرها است داده می‌شود.
$$1 \leq n \leq 100$$
در سطر دوم هر سناریو، $n$ عدد صحیح که مقدار حافظه‌ی متغیرها یعنی $s_1, s_2, \dots, s_n,$ را نشان می‌دهد.
$$1 \leq s_i \leq 4$$
خروجی
در $t$ سطر برای هر سناریو، کمینه حافظه‌ی تلف شده (padding space) در بین تمام ترتیب‌های مختلف برای متغیرها را چاپ کنید.
مثال‌ها
ورودی نمونه ۱
4
3
1 4 1
4
4 2 3 4
1
1
5
3 3 3 3 3
خروجی نمونه ۱
0
1
0
4
سناریو اول در صورت سوال توضیح داده شده.
یک نمونه از ترتیب بهینه، برای سناریو دوم، با ۱ حافظه تلف شده، به صورت زیر است:
تنها ترتیب ممکن، برای سناریو سوم، با ۰ حافظه‌ی تلف شده، به صورت زیر است:
تنها ترتیب ممکن، برای سناریو چهارم، با ۴ حافظه‌ی تلف شده، به صورت زیر است:
ارسال پاسخ برای این سؤال