Polycarp的矩形桌子

内存限制: 128M   时间限制: 1S

题目描述


输入

输出

样例输入

5
1 1 1
2 2 3
3 5 11
100 100 7312
1000000 1000000 1000000000000

样例输出

1
2
9
1174
1000000000000