题目内容

给定$t$组询问，每次询问给出两个正整数$n$和$k$。

在每组询问中，你要找到尽可能少的不同的正整数，满足以下条件：

• 每个正整数在构成同一个数字时，都能用$0$~$k$次。

• 对于区间[$1,n$]里面的每一个数字，都能通过数字之间的组合而“构造”出来、

  这里的“构造”特指求和。更正式地，你需要找到$m$个数字$a_1,a_2,....,a_m$,使得每个$x∈[1,n]$,都能找到至少一组$x=a_1×y_1+a_2×y_2+...+a_m×y_m$（$0≤y_i≤k$）。

  由于数字组合不唯一，请输出最少的数字个数$m$。

输入描述

​ 每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤10^5$)代表数据组数，每组测试数据描述如下：

​ 在一行上输入两个整数$n$($1≤n≤10^9$)和$k$($1≤K≤10^9$)，其含义已在题目中说明。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表最少的满足条件的数字个数。

样例1

输入

3
1 1
3 2
5 2

输出

1 
2
2

说明

对于第一组测试数据，我们最少需要$1$个数字，数字是$1$。此时有$1=1$。

对于第二组测试数据，我们最少需要$2$个数字，数字是$1$和$2$。

此时有$\begin{cases}1=1\\3=1+1\\3=2+1\end{cases}$

对于第三组测试数据，我们最少需要$2$个数字，数字是$1$和$2$。

此时有

$\begin{cases}1=1\\2=1+1\\3=2+1\\4=2+2\\5=2+2+1\end{cases}$