مثلثی از اعداد طبیعی کوچک‌تر از ۱۰۰ شامل حداکثر ۱۰۰۰ خط در اختیار داریم. هر مثلث در سطر اول خود شامل یک عدد، در سطر دوم شامل دو عدد و … در سطر $n$ ام شامل $n$‌ عدد است. یک مسیر کامل مسیری است که از سطر اول مثلث آغاز و به‌یکی از اعداد سطر آخر ختم شود و در هر حرکت از عدد $j$ ام سطر $i$ ام به‌یکی از اعداد $j$ ام یا $j+1$ ام سطر $i+1$‌ ام برود. می‌خواهیم در این مثلث مسیر کاملی را پیدا کنیم که مجموع اعدادی که شامل می‌شود ماکزیمم باشد.

در سطر اول فایل ورودی $m$، تعداد ورودی‌ها آمده است. سپس به ازای هر ورودی در یک سطر $n$ (تعداد سطر‌های مثلث) و در $n$ سطر بعدی به ترتیب سطرهای مثلث آمده‌اند.

به ازای هر ورودی، مجموع اعداد مسیر کامل ماکزیمم مثلث داده شده را در یک سطر بدون فاصله بین سطرها بنویسید.