Ra's Al Ghul, head of the centuries-old League of Shadows, is an international terrorist and assassin whose ultimate goal is a world in perfect environmental balance. He believes that the best way to achieve this balance is to eliminate most of humanity.
As the corruption increased in Gotham city, Ra’s Al Ghul decided to destroy the city using a biological weapon. You, Batman, and your friend James Gordon decided to stop him. Ra's Al Ghul wants to use the train to get a powerful microwave emitter to the main water hub of Gotham City in order to unleash a genetically-engineered virus. In order to stop him, James Gordon wants to reach the main water hub before the train using the Batmobile.
Since you are the best programmer in Gotham city, Gordon asks you to write a program that would calculate the minimum time required to reach the water hub.The following information is known about Gotham City:
The input will start with an integer (1 ≤ T ≤ 100) representing the number of test cases. For each test case, four integers will be given. The first two integers (1 ≤ H, V ≤ 500) represent the number of horizontal roads and the number of vertical roads in Gotham City. The third integer (D ≤ 1000) represents the distance (in meters) between two intersections. The fourth integer (a ≤ 1000) represents the acceleration (in m/s2) of the Batmobile. Following H rows contain V characters each. A character of ‘#’ represents a closed intersection. A ‘G’ character represents Gordon's starting position, and a ‘W’ represents the Water hub intersection; finally, ‘.’ represents an open intersection.
For each test case output one number representing the minimum time (in seconds) required to reach the water hub. The output should be rounded to exactly two decimal points.
3 1 5 1 1 G...W 1 5 10 1 G...W 6 5 10 1 G.... ####. ...#. .#W#. .###. .....
4.00 13.00 67.27