Description

作为我们的天才魔法少女，SKP 在很短的时间内学会了如何骑着拖帕飞行。现在，SKP 心怀大志，准备进军航空业，成立 SKP 国际航空公司。每位搭乘 SKP 国际航空公司航班的旅客除了能够享受优质服务外，还将享受到一份包含 QHJ 全家桶的特色餐食套餐。（如果你在飞机起飞两个小时前在线上服务平台上选择取消机上餐食，则还可以获得 198RMB 代金券一份）

现在 SKP 计划于全球 $N$ 个机场间开设航线。在设计航线时，他需要保证这 $N$ 座机场中的任意两个均可只乘坐 SKP 航空到达（可以中途换乘，但是全程只能搭乘 SKP 航空，此外所有航线都是双向的）。此外一名旅客在从任意一座城市可以乘坐不超过 $K$ 次 SKP 公司的航班到达其余 $N-1$ 座城市（也就是换乘次数不超过 $K-1$ 次）

现在 SKP 想要尽可能少的航线来达到上述目标。SKP 觉得这个问题很难，于是便来向你求助，你能帮帮她吗？

Input

第一行包含一个数字 $T\ (1\le T\le 10^5)$，表示 SKP 进行了 $T$ 次询问。

接下来每一行包含两个整数 $N\ (2\le N\le 300), K\ (1\le K\le N-1)$，含义如上文所示。

Output

对于每一次询问，输出一行一个整数，表示 SKP 最少需要开设的航线数。

Samples

3
2 1
3 1
3 2

1
3
2

Resources

电子科技大学第十五届 ACM 趣味程序设计竞赛