We all know about Amelia Earhart, the famous American aviator. She was the first female pilot to do a solo transatlantic flight. A legend herself, she wanted to do a-round-the-world trip, alone.
Now, it is 1930's and you are a plane navigator. you are given the coordinates of your current airport (x1, y1, z1) and the airport (x2, y2, z2) of your destination, both guaranteed to be distinct and on the surface. Consider, that the earth is a perfect sphere and the center is the origin.
Your task is simple, find the minimum fuel F, which your plane needs to make the flight. You are also told that your plane can only hold an integer amount of fuel and with each unit of fuel it can cross x unit of distance. Also, there is no additional fuel consumption during take-off, landing or taxying.
The first line of the input contains a number T, the number of test cases. Each case contains a number x, the number of units the plane can cross with each unit of fuel. Next line contains 6 integers, x1, y1, z1, x2, y2 and z2.
Print the case number followed by the number of fuel F required to complete the flight.
Input | Output |
---|---|
2 100 0 0 1000 1000 0 0 10 100 100 100 -100 -100 -100 | Case 1: 16 Case 2: 55 |
Consider acos(-1) as the value of pi, if needed.