你正在上一门化学课，正在研究一些化合物，其中恰好有一种是你过敏的。你只有固定的天数来找出是哪一种化合物。你在手臂上设置了若干个测试点。每天，你都要执行以下操作恰好一次：

1. 将每种化合物涂抹在手臂上的某些（可能为空）测试点子集上。你可以将多种化合物涂抹在同一个测试点上。
2. 等待并观察哪些测试点出现了过敏反应。

当且仅当导致你过敏的化合物被涂抹在该测试点上时，该测试点才会出现过敏反应。如果一个测试点出现了过敏反应，它在未来的日子里就不能再被使用了。

请计算为了保证能在给定的天数内准确确定哪种化合物导致你过敏，你手臂上最少需要设置多少个测试点。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。 接下来的 $t$ 行，每行包含两个整数 $n$ 和 $d$ ($1 \le n, d \le 10^{18}$)，描述一个测试用例，其中 $n$ 是化合物的数量，$d$ 是天数。

输出格式

输出 $t$ 行。每行输出一个整数，表示为了在 $d$ 天内发现 $n$ 种化合物中哪一种是过敏原，你手臂上所需的最少测试点数量。请按输入中测试用例的顺序输出答案。

样例

输入 1

1
4 1

输出 1

2