seuOJ476 - 划分(figure version)

在二维平面上有一个面积为 $k$ 的多边形 $S$ ，YiYi 会把这个多边形 $S$ 随机划分成 $n$ 个面积相等的部分，被划分在同一个部分内的区域可以不相邻，然后，YiYi 会按照任意顺序给这 $n$ 个部分编上序号 $1,2,\dots,n$ 。

与此同时，你有一个与 $S$ 相同的多边形 $S'$ ，你也需要把这个多边形 $S'$ 划分成 $n$ 个面积相等的部分，被划分在同一个部分内的区域可以不相邻，同时，你也需要给这 $n$ 个部分编上序号 $1,2,\dots,n$ 。

请注意，你在划分时并不知道 YiYi 的划分方案。

YiYi 想请你求出两次划分中编号相同的部分的重叠的面积的值的可能的最小值是多少。即令 $f(id)$ 表示 YiYi 的划分方案和你的划分方案中编号为 $id$ 的部分的重叠的面积的值，求 $\min\limits_{i=1}^n f(i)$ 可能的最小值是多少。

即确定

\min\limits_{S, S'}\{\max\limits_{p}\{\min\limits_{i=1}^{n}\{|S_i\cap S'_{p_i}| \}\}\}

其中 $p$ 表示长度为 $n$ 的排列的任意形式，即 $\{1,2,⋯,n\}$ ， $|S|$ 表示一个二维平面上的图形 $S$ 的面积。

假设你输出的答案为 $ouf$ ，标准答案为 $ans$ ，你的答案会被认为正确当且仅当 $\frac{|ans-ouf|}{\max(1,ans)}\le 10^{-9}$ 。

评测时你的答案将和四舍五入保留到小数点后 $15$ 位的标准答案比较。

第一行，一个整数 $t(1\le t\le 4·10^4)$ ，代表数据组数。

接下来连续的 $t$ 行，每行两个整数 $k,n(1\le k,n \le 200)$ ，代表多边形 $S$ 与 $S'$ 的面积和划分的份数。

对于每组数据，输出一行 $\min\limits_{i=1}^n f(i)$ 可能的最小值是多少。

输入样例

2
1 1
4 2

输出样例

1.000000000
1.000000000

提示
当 $n=2,k=4$ 时，无论 YiYi 怎么划分多边形 $S$ ，都可以保证 $\min\limits_{i=1}^n f(i)$ 至少为 $1.000000000$ 。