Tinku has a new job at BIT. The job pays well, and provides Tinku with a house to live within BIT. His only job is to deliver goods to Main Building. The goods are to be collected from a pickup point. Therefore, a typical day of work for Tinku begin with him leaving his home, collecting the goods from the pickup point, and ends with him delivering the goods to the Main Building. Pickup points are arbitrary locations in the BIT campus.

The whole BIT campus can be represented as a 2-D plane. Tinku's House, Main Building and pickup points can only be present at integer coordinates. You are given the coordinates of Tinku's house and the Main Building (See the input format carefully). The distance considered is the euclidean distance, i.e, distance from point (a, b) to (c, d) will be sqrt((a-c)^2 + (b-d)^2). A main building can also be a pickup point.

The job contract ensures that Tinku works atmost for H hours. Tinku is new at this job, and is very nervous. ACM people being friendly as always, decide to ease him up by finding the number of possible pickup points such that Tinku is able to finish his work.

Input

First line denotes number of test cases T
T test cases follow
Each test case is formatted as:
First line consist of integers A, B, C, H, V
Tinku's house is at coordinate (A, C), and Main Building is at (B, C)
Tinku works at most for H hours and has walks with a speed of V units/hour

T = 1000
-100 <= A, B, C <= 100
0 < V <= 40
0 < H <= 40

Output

A single line with the number of possible pickup points

Example

Input:
2
1 -1 0 1 3
-5 5 10 2 2
Output:
5
0