مثلثی از اعداد وجود دارد(مانند شکل 2). برنامه‌ای بنویسید که بزرگترین مجموع مسیر از ریشه تا برگ را محاسبه نماید. ریشه بالاترین عدد و برگ در پایین‌ترین قسمت قرار دارند و تنها مسیرهایی مدنظر است که از ریشه شروع شود، از تمام سطوح گذشته و در برگ خاتمه یابد.
## ورودی
در سطر اول تعداد نمونه `t` مشخص شده است. در هر $t< 100$ قسمت بعد در سطر ابتدایی عدد $n<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
```