+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک ربات داریم که در مبدا مختصات قرار دارد! هر بار ربات یک دستور می‌خواند و **یک واحد** بر روی صفحه مختصات دوبعدی طبق آن حرکت می‌کند. ۴ دستور ما ‍‍«**بالا**»، «**پایین**»، «**چپ**» و «**راست**» هستند.  حال به شما تعدادی دستور داده می‌شود و شما باید **همه** آن‌ها را به ربات بدهید. اما می‌توانید **حداکثر** $k$ عملیات انجام دهید. در یک عملیات می‌توانید یکی از دستورها را به یک دستور دیگر تبدیل کنید به شرطی که **جهت مخالف دستور فعلی** نباشد. به عبارت دیگر در یک عملیات نمی‌توانیم «بالا» و «پایین» را به هم و «چپ» و «راست» تبدیل کرد ولی بقیه تبدیل‌ها مجاز هستند. توجه کنید یک دستور را به **تعداد دلخواه می‌توانید** تغییر دهید. برای مثال اگر دو دستور «بالا» + «چپ»‌ را داشته باشیم. می‌توانیم با یک عملیات آن را به «چپ» + «چپ» یا «راست» + «چپ» یا «بالا» + «بالا» یا «بالا» + «پایین» تبدیل کرد اما نمی‌توانیم آن را به «پایین» + «چپ» یا «بالا» + «راست» تبدیل کرد. حال می‌خواهیم بدانیم به ازای سناریوهای مختلف و مستقل هربار ربات پس از انجام دستورات حداکثر چه‌ مقدار می‌تواند به مبدا نزدیک بماند! # ورودی در سطر اول ورودی $t$ یا تعداد سناریوهای مختلف می‌آید. $$ 1 \le t \le 100 \, 000 $$ در $t$ خط بعد در هر خط ۵ عدد طبیعی می‌آید. عدد اول $R$ نشانگر تعداد دستورهای **راست**، عدد دوم $U$ تعداد دستورهای **بالا**، عدد سوم $L$ تعداد دستورهای **چپ** و عدد چهارم $D$ تعداد دستورهای **پایین** است. عددد آخر $k$ هم حداکثر تعداد تغییرهای مجاز را نشان می‌دهد. $$ 0 \le R, U, L, D, k \le 10^9$$ # خروجی در $t$ سطر خروجی در هر سطر یک عدد صحیح برابر با **مجذور** کمینه فاصله ممکن ربات تا مبدا را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 5 1 0 1 0 1 1 2 3 4 2 5 0 4 0 4 4 1 1 5 3 899565959 554564564 149637852 76162365 1000000000 ``` ## خروجی نمونه ۱ ``` 0 0 1 1 0 ``` نمونه‌هام همون قبلیاست! در مثال اول در ابتدا یک «راست» و یک «چپ» داریم که خب در مبدا هستیم و نمی‌تونیم از بیشتر به مبدا نزذیک بشیم. در مثال دوم اگر با دو عملیات دو «پایین» را به دو «راست» تبدیل کنیم آنگاه در هر جهت ۳ دستور خواهیم داشت و در مبدا قرار خواهیم گرفت. در مثال سوم فاصله به طور پیشفرض از مبدا ۱ است و نمی‌توان آن را کاهش داد. در مثال چهارم با تبدیل ۳ «پایین» به ۳ «چپ» به فاصله ۱ از مبدا می‌رسیم.