假设你有 $c$ 枚硬币。其中一枚是伪币，比真币轻。其余所有硬币均为真币，且重量相同。你还有一个双盘天平。在一次称量中，你可以将一些硬币放在一个盘子上，另一些硬币放在另一个盘子上（剩余的硬币不放在任何盘子上），并观察哪个盘子更轻（如果有的话）。你的任务是确定哪一枚是伪币。

听起来很熟悉，对吧？好吧，有好消息也有坏消息。坏消息是天平可能会对你撒谎多达 $k$ 次，而且你无法知道哪些称量结果是真实的。好消息是你可以犯多达 $3k$ 次错误。也就是说，你可以做出多达 $3k+1$ 次猜测，只要其中至少有一次是正确的，你就赢了。

设 $f(n, k)$ 为满足以下条件的最大硬币数量 $c$：如果你有 $c$ 枚硬币，天平最多可能撒谎 $k$ 次，且你最多可以犯 $3k$ 次错误，那么存在一种称量策略，使得无论得到什么结果，你都能在不超过 $n$ 次称量内获胜。

你需要近似求出 $f(n, k)$。具体来说，输出 $\ln f(n, k)$，其中 $\ln$ 是自然对数。如果你的答案与正确答案的绝对差不超过 $10$，则视为正确。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 10^5$)。 接下来的 $t$ 行，每行包含两个整数 $n$ 和 $k$ ($1 \le n \le 10^9$; $0 \le k \le 10^9$)。

输出格式

对于每个测试用例，输出一行，包含一个实数：该测试用例的 $\ln f(n, k)$。如果答案与正确答案的偏差不超过 $10$，则会被接受。

样例

输入 1

2
100 0
100 1

输出 1

109.8612289
106.1174552

说明

在第一个测试用例中，$f(100, 0) = 3^{100}$。这里，答案是 $\ln(3^{100}) = 100 \cdot \ln(3) = 109.8612289 \dots$。 自然对数（以 $e = 2.71828182845904523536 \dots$ 为底的对数）可以使用 C++ 中的 log，Python 中的 math.log 以及 Java 中的 Math.log 计算。