HONDA - Honda and Kagawa

World Cup 2014 has started. Honda wants to watch the matches with his friend Kagawa. So he is planning to visit his friend every night. But just watching the matches is pretty boring. So he will be bringing some snacks. He decided that he will buy chips and juice before going to Kagawa’s house.

Optimum path for travelling

There are many possible path from Honda’s house to Kagawa’s house. But exactly one path is the shortest.

Honda lives at (Hx, Hy) coordinate, where Hx and Hy are positive integers. All the chips shops are located over the x-axis, and all the juice shops are located over the y-axis. Note that, this means, the shop at (0, 0) sells both chips and juice. Kagawa lives at (Kx, Ky) coordinate.

So Honda needs to travel the shop(s) and buy chips and juice before heading towards Kagawa’s house. Since he is really excited about watching the match, he wants to do it as fast as possible. Find the smallest distance he needs to travel.

Note: that a shop is considered a point on the axis. It has no length or width. As a result, even though Honda and Kagawa have their homes at a point with integer coordinates, a shop can have real number in its coordinate. For example, there is a shop at (0, 2.12341) and at (1312.3123, 0).

Input

First line will contain a single integer T (T < 10000) indicating the number of test cases. After that T line will follow. Each line will contain four positive integers: Hx, Hy, Kx, Ky, representing the coordinates of Honda’s house and Kagawa’s house. The coordinates will be less than 10000.

Output

For each case, print the case number and the minimum distance required to travel by Honda. Error less than 10-6 will be ignored.

Sample

Input
5
1 1 2 2
2 1 1 2
1 1 1 3
4 5 10 12
1345 123 123 2

Input
Case 1: 4.242641
Case 2: 4.242641
Case 3: 4.472136
Case 4: 22.022716
Case 5: 1473.312255

Hints

In the first case, the optimum route is (1,1) → (0,0) → (2,2)

In the second case, the optimum route is (2,1) → (1,0) → (0,1) → (1,2)

In the third case, the optimum route is (1,1) → (0.5,0) → (0,1) → (1,3)


Added by:forthright48
Date:2014-06-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2018-06-16 10:51:32
done forget about correct output format !!
2015-08-08 06:43:32 Samiul
@farziengineer: No it won't.
2015-06-06 10:11:26
will brute force work in this question
Please reply
2014-08-12 08:48:20 ^_^
The toughest problem ever tried... 😂
2014-07-12 20:06:35 sunshine
Getting wrong answer again n again ny tricky case
AC foolish mistake TOO Easy

Last edit: 2014-07-12 21:10:31
2014-06-25 20:22:42 Bhavik
i am feeling embarassed after realizing my mistake.AC now

Last edit: 2014-06-26 20:07:35
2014-06-23 18:08:20 Samiul
Sorry about that. This is the first time I am uploading a picture with statement. Took me a while to understand what Francky meant by "upload files" feature. I was searching for it in "edit problem" section.

Now it should be alright. Thank you for notifying issue.
--ans(Francky)--> Issue fixed. Thanks.

Last edit: 2014-06-23 18:19:13
2014-06-23 18:06:44 :|
you have made your image private in google drive, change the privacy of the image!
--ans(Francky)--> No thanks for extern solution. Please, psetter should use "upload files" from spoj server.

Last edit: 2014-06-23 17:08:12
2014-06-23 18:06:44 [themighty] deathsurgeon
The image is not loading in my browser. Am I the only one facing this problem?
--ans(Francky)--> psetter should use "upload files" capability. Hope it will be soon changed.

Last edit: 2014-06-23 17:06:48
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.