Description

你已经迷上了最新流行的集换式卡牌游戏——PokeCraft：The Gathering。你已经掌握了所有规则！你组建了均衡、进攻型和防御型的套牌！你在网络论坛上激烈争论各种卡牌的优劣！你参加了各种锦标赛！现在，随着官方刚刚宣布将在 2010 年推出一套巨大的新卡包，你决定要收集齐所有新卡！幸运的是，你头脑中仅存的理智还在思考：这究竟要花多少钱？

新卡包中共有 $C$ 种不同的卡牌。卡牌将以“补充包”的形式出售，每个补充包包含 $N$ 张不同种类的卡牌。补充包的组合方式有很多种，每包内不会有重复卡牌。每次你购买一个补充包，你会以等概率获得所有可能的组合之一。你会一包一包地买，直到你拥有所有 $C$ 种卡牌为止。你想知道，平均而言，你需要买多少包补充包才能集齐所有卡牌？

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据，每组一行，包含两个整数 $C$ 和 $N$。

Output Format

对于每组测试数据，输出一行，格式如下：

Case #$x$: $E$

其中 $x$ 为测试编号（从 1 开始），$E$ 为你期望需要购买的补充包数量。只要你的答案的绝对误差或相对误差不超过 $10^{-5}$，就会被接受。

2
2 1
3 2

Case #1: 3.0000000
Case #2: 2.5000000

Hint

限制条件

• $1\leq T\leq 100$

小数据集（10 分）

• $1\leq N\leq C\leq 10$

大数据集（20 分）

• $1\leq N\leq C\leq 40$