German is the chief of the Rescuers and Principal Lifesavers of the ocean (RPL), he is in charge of commanding the search of survivors on a range given after a ship sinks, this range is established from the time that the ship sunk, he will always know this value, because he is magnificent in maths, however, he isn't good calculating the perfect searching range, this causes problem in rescuing survivors as the ship may exceed the limit of the area of searching.

It is known that German will always send three ships to make the rescue effective, as he can't send all his ships, he wants to maximize the area of the three ships covers. The ships of German aren't sophisticated, so they will be going on a single direction (always) and a constant speed. The ships moves every unit of time.

We say that an area is covered when the area made by the three points (triangular area) is lesser or equal than the maximum area that German knows.

German will give you the initial coordinates of all three ships (given in 2D), the direction the ship will be going and the speed per hour. The direction of the rescuer ship will always be to north, south, east or west and the maximum area of search. Please have in count that the area covered by the three ships must NOT exceed the area that German gives to you.

Input

The first line of the test data will start with an integer T representing the T test cases, then, T×4 Lines will follow, each of the following lines will contain, respectively, the maximum area of searching, the next three lines will contain, each, three integers and a string, denoting the coordinates the ship is in, the direction and the speed.

Output

You must output the string “Scenario #i: “ where i is the number of test case you're analyzing, followed by the time that the three ships will cover the maximum possible area (without exceeding it). Time will always be discrete.

Example

Input:
2
150
1 4 north 2
2 0 south 2
3 1 east 2
12
0 -2 north 1
0 0 north 2
0 0 east 3

Output:
Scenario #1: 5
Scenario #2: 2

Explanation of the second sample

At hour two, the ship 1 will be at position (0, 0), the ship 2 will be at position (0, 4) and the ship 3 will be in (6, 0), computing the area of a triangle, we will have a value of 12, as we know that there is no other possible area that satisfies the maximum without exceeding it, we output 2.

It is guaranteed that all three ships will always be distancing themselves, then, the next area will always be bigger.

Constraints

1 ≤ T ≤ 100

-10⁶ ≤ X, Y ≤ 10⁶

1 ≤ Speed ≤ 10

Small Input (30%)

For the “small” input, the triangles will always be rectangled triangles, making the area of them easier to calculate.

1 ≤ Max_Area_Of_Searching ≤ 10³

Large Input (70%)

Points will form any triangle, time-limit is heavier on these files.

10³ ≤ Max_Area_Of_Searching ≤ 10⁹