
ZOJ Problem Set  3473
Radio is a magical thing, isn't it? There are many (technically, it's infinite) radio stations staying in the universe, and in our case, they are arranged in a matrix. The matrix starts from our planet  the earth, that means we can give coordinates to each radio station in the matrix grid, and the one on the earth has the coordinates (1, 1, 1). So we can identify each radio station by its coordinates (x, y, z). Here x, y and z are all positive integers. Every radio station has two states, receiving state and sending state. At the beginning, all stations except the one at (1, 1, 1) stay in receiving state, while the one at (1, 1, 1) initially stays in sending state. While in sending state, station at (x, y, z) will continuously send message which has a message value S_{x, y, z} to all the other stations, and the message been sent out is encoded by this station's coordinates (x, y, z), that means only the stations which have coordinates (x', y', z') (here x' is multiple of x, y' is multiple of y, z' is multiple of z, but (x', y', z') cannot be the same to (x, y, z) ) can decode the message sent by station (x, y, z). Here S_{1, 1, 1} = 1. While in receiving state, station at (x, y, z) (here x, y, z cannot equals to 1 at the same time) will always check whether it has received all the messages it can decode. If this station (x, y, z) finds that all the messages it can decode has been received, it will change its state to sending state, and its S_{x, y, z} equals to the maximum S_{x, y, z} value it had decoded plus one. Now for coordinates (x, y, z), we want to know the sum of all the messages sent from stations (x', y', z'). Here 1 ≤ x' ≤ x, 1 ≤ y' ≤ y, 1 ≤ z' ≤ z. InputThere are at most 100000 test cases, each test case in a line, each line contains three integers x, y and z. Here 1 ≤ x, y, z ≤ 500000. OutputFor each testcase, you should output the sum of all messages sent from stations whose coordinates (x', y', z') fulfill 1 ≤ x' ≤ x, 1 ≤ y' ≤ y, 1 ≤ z' ≤ z in one line. Sample Input2 2 2 2 3 2 2 1 3 5 3 4 Sample Output20 32 13 220 Author: FAN, Yuzhe Contest: ZOJ Monthly, February 2011 