Golden Ceiling

Time limit1sMemory limit128 MB

Summary

Given a box and a tilted plane forming a ceiling, compute the total gold-leaf area combining the plane's surface inside the box and the flat ceiling area where the plane exceeds the ceiling height, rounded up.

Level: Hard8 of 10
Topics: Geometry, Math, Implementation
Solved: No attempts yet

Problem

A rectangular atrium occupies the box 0 <= x <= L, 0 <= y <= W, 0 <= z <= H. One corner is at (0, 0, 0), and the opposite corner is at (L, W, H).

The tilted ceiling lies on the plane Ax + By + Cz = D. The plane is not vertical and passes through the inside of the box. It may also touch the floor or the original ceiling.

The surface that must be covered with gold leaf is defined as follows.

Where the plane lies between the floor and the original ceiling, cover that part of the plane.
Where the plane lies above the original ceiling, cover the original horizontal ceiling there.
Where the plane lies below the floor, there is no ceiling surface to cover.

Write a program that computes the total area that must be covered.

Input

The first line contains the number of data sets P. (1 <= P <= 1000)

Each data set is given on one line as seven space-separated values L W H A B C D. L, W, and H are the length, width, and height, and they are all positive. A, B, C, and D are the coefficients of the tilted plane

Ax + By + Cz = D.

Only points with 0 <= x <= L, 0 <= y <= W, and 0 <= z <= H are considered. The plane is not vertical, so C >= 1.0 always holds.

Output

For each data set, output one line containing the area that must be covered with gold leaf, rounded up to the nearest integer number of square joonmin.

Examples1

Example 1

Input

3
10 12 15 -1.3 1 1.1 3.5
10 12 10 -1.3 1 1.1 11
13 9 10 -1.3 1 1.1 0

Expected output

166
164
144