Input
4
2 2 1
2 2 3
2 2 2
2 2 4
Output
5
5
4
0