芳芳学了动态规划之后，觉得数字三角形问题太简单了。然后，爱思考的芳芳想了一个看上去复杂一点的问题，假如对最后的结果对100取余，该怎么计算呢？聪明的芳芳，想都没想就秒杀了，芳芳想考考你，你可以解决吗？

多组输入。不超过10组数据，输入数据的第1行是数字三角形的行数n，1≤n≤24。接下来n行是数字三角形各行中的数字。所有数字在0..10000之间。

每组数据输出一个数字，对100取余后，最大的结果。

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

30
2