In the honey bee hive of flora land our chef bee was a bit lazy. So instead of going out, she decided to steal honey from its neighbors. This continued for a while but then this laziness made her fat. Now she can fly only for unit d distance.

The honey bee hive, just like a regular hive is made up of MxN regular hexagonal compartments where the length of edge of hexagonal is k unit distance. You have to calculate from how many compartments she can potentially steal honey in single flight if the co-ordinate of center of leftmost and bottom most compartment is (0,0) and bee is currently at (x,y).

Note: Assume that the honey is stored at the center of the hexagonal compartments and bee has to come back to its original position every time after stealing honey from a compartment.

Input

The first line of the input contains an integer T denoting the number of test cases, for each test case enter

Maximum distance travelled by bee, current position of bee i.e. (x,y), size of hive (MxN), length of edge of hexagon.. All seperated by a single space.

Output

For each test case, output a single line with number of compartments accessible to bee.

Constraints

• 1 = T = 100
• 1 = M = 100
• 1 = N = 100
• 1 = D = 100

Example

Input:

2

5 0 0 100 100 1

6 2 3 15 20 1

Output:

2

6

Explanation

Case 1 : Since bee is at position (0,0) she can reach out to the compartment centered to at

(1.73,0), (0.86),1.5)

Case 2 : Since bee is at position (2,3) she can reach out to the compartment centered to at

(2.59,1.5), (0,3), (0.88,1.5), (3.46,3), (0.88,4.5), (2.59,4.5)