题目描述

在魔法学院的期末考试中，江桥面临着一场特殊的魔法考核。他需要在 $n$ 天内完成一系列魔法实验，最终要成功炼制出 $m$ 颗具有强大魔力的魔法水晶。

初始时，江桥手中仅有 $1$ 颗魔法水晶的雏形。在这 $n$ 天的实验过程里，江桥每天最多可施展一次特殊魔法。每次施展魔法时，他可以付出 $c$ 点魔力值（$c \geq 1$，且 $c$ 为整数），将当前手中所有的魔法水晶雏形进行复制。具体规则是：若当前江桥手中有 $a$ 颗魔法水晶雏形，付出 $c$ 点魔力值施展魔法后，魔法水晶雏形的数量会变为 $(c + 1) \times a$ 颗。

江桥希望以最小的魔力消耗完成考核，恰好炼制出 $m$ 颗魔法水晶。请你帮江桥计算出达成目标所需的最小魔力代价。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$ 代表数据组数，对于每组测试数据：

在一行上输入两个整数 $n,m$，表示魔法实验的天数和最终需要炼制出的魔法水晶数量。

输出格式

对于每一组测试数据，新起一行输出一个整数，表示江桥炼制出 $m$ 颗魔法水晶所需消耗的最小魔力值。

3
1 5
2 6
8 27720

4
3
27

样例解释

无

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq T \leq 3 \times 10^5,1 \leq n,m \leq 10^{6}$。