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

مثلثی از اعداد وجود دارد(مانند شکل). برنامه‌ای بنویسید که بزرگترین مجموع مسیر از ریشه تا برگ را محاسبه نماید. ریشه بالاترین عدد و برگ در پایین‌ترین قسمت قرار دارند و تنها مسیرهایی مدنظر است که از ریشه شروع شود، از تمام سطوح گذشته و در برگ خاتمه یابد.

ورودی

در سطر اول تعداد نمونه $t$ مشخص شده است. در هر $t \lt 100$ قسمت بعد در سطر ابتدایی عدد $n \lt 100$ تعداد سطوح مثلث آورده شده است. در $n$ خط دنباله‌ی آن در خط $i$ام که بین $1$ تا $n$ است $i$ عدد بین $0$ تا $99$ دریافت می‌شود.

خروجی

برنامه‌ی شما باید به ازای هر نمونه یک عدد شامل بزرگترین مجموع مسیر از ریشه تا برگ را محاسبه نماید.

مثال

ورودی نمونه ۱

1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

خروجی نمونه ۱

30