凯旋三兵

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

B君有n个球排成一个环形,开始时这n个球都是白色。
B君会对这些球进行若干次染色操作。
每次操作,B君会随机等概率地选择的一个区间:先随机选择一个球作为起点,再 随机选择一个球作为终点,每个球被选为起点和终点的概率相同且两次选择独立。这 意味着一共有$n^2$种起点和终点的组合。
B君会从起点开始沿顺时针方向将途中的所有球都染成黑色,直到终点为止(起点 会被染色,但终点不会)。如果起点和终点重合,那么B君会将所有的n个球都染成黑 色"
当黑色的球达到至少m个,B君就会停止染色。
问B君期望需要染色多少次。

Input

包含至多101组测试数据。
第一行有一个正整数,表示数据的组数。
接下来每一行表示一组数据,包含两个整数n,m,含义如前所述。 保证1<=m<=n<=40。

Output

对于每组数据输出一行,为四舍五入保留12位小数后的答案。 注意:你的输出必须要和参考答案完全一致才算正确。

Sample Input

5 5 1 5 2 5 3 5 4 5 5

Sample Output

1.000000000000 1.208333333333 1.491600790514 1.923126739774 2.710272469712

Hint

jiangzijing2015

Source

2016年中国大学生程序设计竞赛(合肥)-重现赛(感谢安徽大学)

提交代码