A :: Interstellar

Time Limit: 5 Seconds Memory Limit: 65536 KB

We are in future, 2050, where humans have been conquered the space and people are spread out between different planets. For having a nice-looking space, all planets have been moved in a way that if you look at the new space from sun, you'll see a cube of planets each laid on a positive integer coordination in the cube. The ordered planets are bounded in a X*Y*Z cube. Note that in each coordination there is exactly one planet.

Visiting your friends are now even harder and more expensive than any time and you need to have inter-planet flights with jets. Since having high-speed jets really matters in space trips, commercial jets have high-speed (half of speed of light!) but with one limitation that they cannot change their direction and can move only in one direct line between their source and destination. Traditionally, if your jet passes another planet during the trip, you have to pay 1 planeto (new interstellar currency) “space toll road”. For example if you want to trip from (1,1,1) to (5,9,5) you have to pay 3 planetos since you'll visit planets, (2,3,2), (3,5,3), (4,7,4).

Given X, Y and Z, the size of cube of planets, we are interested to know the summation of planetos that will be paid, if we travel between all pairs of planets.

Input

In first line of input there is T, number of test cases.

Each test case contains three positive integers, X, Y, Z. Its guarantee that the number of planets is less than 10^6.

Output

For each output print the summation of planetos will be paid by visiting every pair of planets modulo 1000000007.

Sample Input

Sample Output

0
1
17438

Submit

Source: 13th Iran Nationwide Internet Contest - SBU