说明

HYX 经常不回 Hank 的消息，Hank 为此非常郁闷，于是打算去商店买个寂寞。

因为寂寞是特殊物品，商店出售寂寞的方式非常特殊：
商店一共提供 k 种类型的套餐，每种套餐各包含1~k个寂寞。你只能选择一种套餐购买一次或多次。

Hank想购买 n 个寂寞，但是需要使购买套餐次数最小。

例如 Hank 想购买 8 个寂寞，商店提供 7 种套餐，那么 Hank 可以购买 2 次包含 4 个寂寞的套餐。

请帮助 Hank 判断需要购买套餐的最小次数。

输入格式

第一行包含一个整数t（1≤t≤1000）作为测试组数，接下来是 t 组测试数据。
每个测试包含两个正整数 n (1≤n≤10^9) 和k (1≤k≤10^9)

输出格式

输出每组数据的答案，即购买同种套餐的最小次数

样例

4
8 7
8 1
6 10
999999733 999999733

2
8
1
1