Input
4
1 1 1
1 6 1
2 2 2
100 100 100
Output
1
4
4
165