Ellipse Coverage

An ellipse is a figure on a plane where the sum of the distances from any point on its perimeter to two fixed points is constant. The two fixed points are called foci (plural of focus). In this problem we are interested in the number of points with integral coordinates that lie strictly inside of the given ellipse. 

The foci are (x1, y1) and (x2, y2), and the fixed sum of distances is d. 

Constraints 
x1 , y1, x2, y2 will be between -100 and 100, inclusive. 
d will be between 1 and 200, inclusive.  
The arguments will define a valid ellipse with positive area. 


Input
The first line contains a single integer T tells that there are T cases in the problem. Then for each case, there are 5 integers, x1, y1, x2, y2 and d in order.

Output
The number of points with integral coordinates that lie strictly inside of the given ellipse. 

Sample Input
3
0 0 0 0 4
-3 0 3 0 10
13 -23 49 91 200

Sample Output
9
59
25187