**题意简述**

有一只小羊，本来住在原点（0，0)(使用数学里的平面直角坐标系)，后来突然出现在了（x,y)这个点。

因为它在梦游，所以它每一步都会在上下左右里随机行走。（每次只能走一格）

但是有两只狗子在帮助它回到（0，0)，小羊不会选择狗子在的位置，狗子也不能走到和羊/另一只狗同一个格子，狗子每回合可以瞬间移动。

也就是说，狗子是小羊的路障，可以在小羊行走前，挡住最坏的两个可能性，让小羊在两个较好的方向中选择。

问狗子在最机智的情况下，小羊从（x，y）点回到家（0，0）的数学期望值是几步。

**Problem**

Bleatrix Trotter is a sheep who lives in a two-dimensional field that is an infinite grid of unit cells. Her home is in a unit cell that we denote as (0, 0) — that is, all coordinates are given relative to Bleatrix’s home cell. However, because she has been sleepwalking, she is currently in the unit cell at the coordinates (X, Y) — that is, in a cell X columns east of, and Y rows north of, her home cell. The two sheepdogs who have been assigned to protect Bleatrix have just noticed that she is missing, and now they want to herd her back to her home cell.

Before each of Bleatrix’s moves, the two sheepdogs can move to any grid cells that they want, except that they cannot both move to the same cell, and neither one can move to Bleatrix’s current cell. Once the sheepdogs are in place, Bleatrix, who is sleepwalking, will make a random unit move in a direction that would not take her into a cell with a sheepdog. That is, she takes the set of four possible unit moves (north, south, west, east), discards any that would move her into a cell with a sheepdog, and then chooses uniformly at random from the remaining moves. Then the sheepdogs can position themselves again, and so on (notice that, unlike Bleatrix, the sheepdogs do not have to make unit moves).

Once Bleatrix arrives at her home at (0, 0), she stops sleepwalking, wakes up, and grazes peacefully, and does not make any more moves thereafter.

If the sheepdogs coordinate their movements to minimize the expected number of Bleatrix’s moves to reach her home, what is that expected number?

**Input**

The first line of the input gives the number of test cases, T. T test cases follow. Each case consists of one line with two integers X and Y, representing the coordinates of Bleatrix’s starting cell, as described above.

**Output**

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the expected number of Bleatrix’s moves, as described above. y will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the Competing section of the FAQ for an explanation of what that means, and what formats of real numbers we accept.

**Limits**

Time limit: 20 seconds per test set. (10 seconds per test run.)

Memory limit: 1GB.

(X, Y) ≠ (0, 0).

**Test set 1 (Visible)**

1 ≤ T ≤ 48.

-3 ≤ X ≤ 3.

-3 ≤ Y ≤ 3.

**Test set 2 (Hidden)**

1 ≤ T ≤ 100.

-500 ≤ X ≤ 500.

-500 ≤ Y ≤ 500.

**Sample**

**Input**

1

-1 1

**Output**

Case #1: 4.000000

Notice that the values of X and/or Y may be negative. An X value of -1, for example, means that the cell is one unit west of Bleatrix’s home cell. (Similarly, a negative value of Y means the cell is south of Bleatrix’s home cell.)

In the sample case, Bleatrix starts off one cell to the north of, and one cell to the west of, her home. Before she makes her first move, the two sheepdogs could position themselves in cells (-2, 1) and (-1, 2). Then, whichever direction she might choose, she would end up only one step away from her home… but the sheepdogs could not guarantee that she would go there on her next move! The remaining details are left for you to discover.

```
/*
从（1，1）走回原点时：
步数=0.5*2+0.5^2 * 2x2 + 0.5^3 *2x3……
即 sum 2*(0.5^j*j),j=1..infinity
↑用mathpad求极限确实是4……
*/
#include <iostream>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;
const int N = 505;
long double dp[N][N];//表示从该点走到坐标原点平均需要多少步
void pre()
{
dp[0][0] = 0.0;
dp[1][0] = 3.0;
dp[1][1] = 4.0;//可参考样例或者自己求一下极限
for(int i = 2; i<N; i++)
{
dp[i][0] = (2.0*dp[i-1][0] + dp[i-1][1] + 6.0)/3.0;
/*
dp[i][0]=(dp[i-1][0]+dp[i][1])/2+1
这里dp[i][1]还未计算出来，所以需要迭代一下
dp[i][1]=(dp[i][0]+dp[i-1][1])/2+1
dp[i][0]=0.5dp[i-1][0]+0.25dp[i][0]+0.25dp[i-1][1]+1.5
0.75dp[i][0]=0.5dp[i-1][0]+0.25dp[i-1][1]+1.5
等式两边同时除以3再乘4即可
*/
for(int j = 1; j<i; j++)
dp[i][j] = (dp[i][j-1] + dp[i-1][j])/2.0 + 1.0;//可能在水平方向接近原点一步
//也可能在垂直方向接近原点一步
dp[i][i] = dp[i][i-1] + 1.0;//只用一步必然可以走到dp[i][i-1]
//（相对原点的等价位置算同一种）
}
return;
}
int main()
{
pre();//首先dp出范围内的每个点（四个象限是对称的，算一个象限即可）走回原点要多少步
//然后把输入的x和y转移到对应的第一象限位置直接给出答案
cout << fixed << setprecision(8);
int T,casei;
cin >> T;
while(T--)
{ casei++;
int x, y;
cin >> x >> y;
x = abs(x);
y = abs(y);
if(x < y) swap(x, y);
cout << "Case #" << casei << ": "<<dp[x][y]<<endl;
}
return 0;
}
```