YELBRICK - The Yellow Brick Road

After Dorothy’s memorable adventure in the Land of Oz, traffic along the Yellow Brick Road got really intense, making some sections of it nearly impossible to cross because of the holes along the road. The Land of Oz engineers are having trouble to pave this road, because the yellow stone is in short supply, forcing them to buy stones from different suppliers. As you already know, every road in the Land of Oz must be built using bricks that are perfect and identical cubes. To maximize the durability of the road, it also must be built using the least number of bricks possible. The problem is that each supplier provides stones of different sizes, that must be cut in order to make the bricks for the road.

Can you help the engineers to find which is the best brick size to use to maximize the road durability?

Input

Each test case is given using several lines. The first line contains an integer N representing the number of different suppliers of yellow stone (2 ≤ N ≤ 1000). For simplicity, we assume that the engineers will buy exactly one stone from each supplier. Each of the next N lines contains three integers Ai, Bi, Ci (0 < Ai, Bi, Ci ≤ 1000, 1 ≤ i ≤ N) that describe, respectively, the width, height and depth of each stone provided by the i-th supplier. The last test case is followed by a line containing one zero.

Output

For each test case, print one line containing the minimum number of identical cubes that can be cut from the given stones.

Example

Input:
2
1 2 3
4 5 6
2
4 4 4
2 2 2
0

Output:
126
9

Added by:Paulo Costa
Date:2012-02-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ICMC-USP

hide comments
2024-05-05 06:49:45
answer can overflow 32 bits
2016-10-31 11:23:49
can anyone make me understand what is to be done in this question
2016-10-22 20:33:46 marwan akkad
to solve this there are no remainders
2016-09-16 18:57:15
gcd for a loop;)
2016-08-10 12:32:29 Min_25
Since the test cases are too weak, we can get AC with both of the following assumptions:
1. Every stone must be cut into AxAxA cubes. (there are no remainders)
2. Every stone can be cut into an AxAxA cube. (there can be remainders)
2015-01-30 18:38:07 Soumik Chatterjee
Do we have to use up the blocks from suppliers wholly or could we take the cubes from it and leave the remainder?
2013-03-27 09:02:41 :D
I tried to rephrase it a little. It meast that there is exactly one stone of each "type". And you must find an integer A such that all of them can be cut into AxAxA cubes and the number of cubes is minimal.
2013-03-27 07:53:35 joud zouzou
"For simplicity, you can assume that the engineers will
buy one stone from each supplier."
can anyone explain?
2013-02-01 16:21:32 Ouditchya Sinha
Good question... AC :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.