+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
یک ربات داریم که در مبدا مختصات قرار دارد! هر بار ربات یک دستور میخواند و **یک واحد** بر روی صفحه مختصات دوبعدی طبق آن حرکت میکند. ۴ دستور ما «**بالا**»، «**پایین**»، «**چپ**» و «**راست**» هستند.
![توضیح تصویر](https://quera.org/qbox/view/ZrQ19Mb5Tz/E.png)
حال به شما تعدادی دستور داده میشود و شما باید **همه** آنها را به ربات بدهید. اما میتوانید **حداکثر** $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
```
نمونههام همون قبلیاست!
در مثال اول در ابتدا یک «راست» و یک «چپ» داریم که خب در مبدا هستیم و نمیتونیم از بیشتر به مبدا نزذیک بشیم.
در مثال دوم اگر با دو عملیات دو «پایین» را به دو «راست» تبدیل کنیم آنگاه در هر جهت ۳ دستور خواهیم داشت و در مبدا قرار خواهیم گرفت.
در مثال سوم فاصله به طور پیشفرض از مبدا ۱ است و نمیتوان آن را کاهش داد.
در مثال چهارم با تبدیل ۳ «پایین» به ۳ «چپ» به فاصله ۱ از مبدا میرسیم.
ربات: نزدیکتر و نزدیکتر