KIDZEE1O - Kings on an Infinite Chessboard

no tags 

Given an infinite chess board and a starting position (r1, c1) find how many moves a traditional chess king will need to move to another position (r2, c2). In case you do not know how a chess king moves, a traditional chess king can go to any of its 8 adjacent cells in a single move as shown in the picture below:

একটি অসীম আকারের দাবার বোর্ডে রাজার শুরুর অবস্থান (r1, c1)  দেয়া আছে। বের করতে হবে, কত চালে দাবার রাজা (r2, c2) অবস্থানে যেতে পারবে। যদি তোমার না জানা থাকে দাবার রাজার চাল কী, একটি দাবার রাজা এক চালে তার চারপাশের ৮ টি ঘরের যেকোনো একটি ঘরে যেতে পারে, নিচে দেখানো ছবির মত।

Kings move in chess board

Input

The first line of input file contains the number of test cases T (T ≤ 50), then T lines follow. Each line contains 4 integers: r1, c1, r2, c2, where, (r1, c1) is the co-ordinate of the starting cell and (r2, c2) is the co-ordinate of the destination cell (0 ≤ r1, c1, r2, c2 ≤ 1000).

ইনপুট ফাইলের প্রথম লাইনে থাকবে টেস্ট কেসের সংখ্যা T (T≤50), এবং এর পরে T সংখ্যক লাইন থাকবে। প্রতি লাইনে 4টিপূর্ণ সংখ্যা থাকবে: r1,c1,r2,c2, যেখানে, (r1,c1) হচ্ছে শুরুর ঘরের স্থানাংক আর (r2, c2) হচ্ছে শেষের ঘরের স্থানাংক। (0 ≤ r1, c1, r2, c2 ≤ 1000).

Output

For each case, print a line containing “Case X: Y”, without the quotes, where X is the test case number starting from 1, and Y is the number of moves a traditional chess king will need to reach (r2, c2) from (r1, c1). Check sample input and output sections for more details.

প্রতিটি কেসের জন্য একটি করে লাইন প্রিন্ট করতে হবে যেখানে “Case X: Y” লেখা থাকবে, কোন কোটেশন চিহ্ন ছাড়া। এখানে X হচ্ছে 1 থেকে শুরু করে টেস্ট কেসের নম্বর এবং Y হচ্ছে (r1, c1) থেকে (r2, c2)  তে পৌঁছাতে দাবার রাজার প্রয়োজনীয় চালের সংখ্যা । নমুনা আউটপুটে আরো বিস্তারিত দেখতে পারো।

Example

Input:
3
1 1 3 3
1 2 6 9
42 468 335 501

Output:
Case 1: 2
Case 2: 7
Case 3: 293


Added by:Shafaet
Date:2013-01-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem - Used for Junior Training