Limits 1s, 512 MB

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.

Input

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.

  • 1<=T<=1000
  • 1.0<=x<=1000000.0
  • -1000000<=x1,y1,z1,x2,y2,z2<=1000000

Output

Print the case number followed by the number of fuel F required to complete the flight.

Sample

InputOutput
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.

Submit

Login to submit.

Statistics

75% Solution Ratio
user.371955Earliest, Aug '19
crop_NCodeFastest, 0.0s
user.371955Lightest, 131 kB
ovis96Shortest, 372B
Toph uses cookies. By continuing you agree to our Cookie Policy.