#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector vi;
typedef pair<int, int> pi;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <= b; i++)
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// v.push_back(make_pair(y1,x1));
// v.push_back(make_pair(y2,x2));
// int d = v[i].first+v[i].second;
// can be shortened as follows:
// v.PB(MP(y1,x1));
// v.PB(MP(y2,x2));
// int d = v[i].F+v[i].S;
long long solve(long long s, long long n) {
long long coins = 0;
// if (s == 1) {
// // coins = 1;
// return 1;
// }
bool odd = false;
if (s % 2 == 1) {
odd = true;
s = s - 1;
}
long long cur_sum = 0;
if (s <= n and s > 0) {
coins += 1;
}
else if (s > n) {
coins += (s / n);
cur_sum += (coins * n);
for (long long i = n - 2; i >= 2; i -= 2) {
while (cur_sum + i <= s) {
cur_sum += i;
coins++;
}
}
}
if (odd)
coins++;
return coins;
}
int main() {
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif
FIO;
int t;
cin >> t;
while (t--) {
long long s, n;
cin >> s >> n;
long long coins = solve(s, n);
cout << coins << endl;
}
return 0;
}