t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    ans = 0
    if n % 2 == 1:
        n -= k
        ans = 1
    k -= 1
    ans += (n + k - 1) // k
    print(ans)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    long long ans = 0;
    if (k > 1) {
      sort(a.begin(), a.end(), greater<int>());
      ans = accumulate(a.begin(), a.begin() + k + 1, 0LL);
    } else {
      int l = *max_element(a.begin(), a.end() - 1);
      int r = *max_element(a.begin() + 1, a.end());
      ans = max(l + a.back(), r + a[0]);
    }
    cout << ans << '\n';
  }
}

from bisect import bisect_left

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    ans = 0
    for k in range(1, n):
        x = m - bisect_left(a, k)
        y = m - bisect_left(a, n - k)
        ans += x * y - min(x, y)
    print(ans)

#include <bits/stdc++.h>
 
using namespace std;

using li = long long;

const int B = 60;
const li INF = 1e18;

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  array<array<li, B>, B> dp;
  for (int i = 0; i < B; ++i) {
    for (int j = 0; j < B; ++j) {
      dp[i][j] = INF;
    }
  }
  dp[0][0] = 0;
  for (int x = 0; x < B; ++x) {
    for (int i = B - 1; i >= 0; --i) {
      for (int j = B - 1; j >= 0; --j) {
        if (dp[i][j] == INF) continue;
        if (i + x < B) dp[i + x][j] = min(dp[i + x][j], dp[i][j] + (1LL << x));
        if (j + x < B) dp[i][j + x] = min(dp[i][j + x], dp[i][j] + (1LL << x));
      }
    }
  }
  int t;
  cin >> t;
  while (t--) {
    li x, y;
    cin >> x >> y;
    li ans = INF;
    for (int i = 0; i < B; ++i) {
      for (int j = 0; j < B; ++j) {
        if ((x >> i) == (y >> j)) ans = min(ans, dp[i][j]);
      }
    }
    cout << ans << '\n';
  }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
const int K = 31;
 
int add(int x, int y)
{
    x += y;
    while(x >= MOD) x -= MOD;
    while(x < 0) x += MOD;
    return x;
}
 
int sub(int x, int y)
{
    return add(x, -y);
}
 
int mul(int x, int y)
{
    return (x * 1ll * y) % MOD;
}
 
int binpow(int x, int y)
{
    int z = 1;
    while(y)
    {
        if(y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}
 
int dp[K][2][2][2];
 
int choose2(int n)
{
    return mul(n, mul(sub(n, 1), binpow(2, MOD - 2)));
}   
 
void solve()
{
    int n, m, A, B;
    cin >> n >> m >> A >> B;
 
    memset(dp, 0, sizeof dp);
    dp[0][0][0][0] = 1;
    for(int i = 0; i + 1 < K; i++)
        for(int f1 = 0; f1 <= 1; f1++)
            for(int f2 = 0; f2 <= 1; f2++)
                for(int fx = 0; fx <= 1; fx++)
                {
                    int d = dp[i][f1][f2][fx];
                    if(!d) continue;
                    int j = K - 2 - i;
                    int curA = (A >> j) & 1;
                    int curB = (B >> j) & 1;
                    for(int bit_a = 0; bit_a <= 1; bit_a++)
                        for(int bit_b = 0; bit_b <= 1; bit_b++)
                            for(int bit_x = 0; bit_x <= 1; bit_x++)
                            {
                                if(f1 == 0 && bit_a == 1 && curA == 0) continue;
                                if(f2 == 0 && bit_b == 1 && curB == 0) continue;
                                if(fx == 0 && bit_x == 1 && (bit_a == 0 || bit_b == 0)) continue;
                                int nf1 = max(f1, bit_a ^ curA);
                                int nf2 = max(f2, bit_b ^ curB);
                                int nfx = max(fx, bit_x);
                                int& d2 = dp[i + 1][nf1][nf2][nfx];
                                d2 = add(d2, d);
                            }
                }
    int pairs_of_pairs = 0;
    for(int i = 0; i <= 1; i++)
        for(int j = 0; j <= 1; j++)
            pairs_of_pairs = add(pairs_of_pairs, dp[K - 1][i][j][1]);
 
    int comb_a = sub(binpow(2, n), 2);
    int comb_b = sub(binpow(2, m), 2);
 
    int ans = mul(pairs_of_pairs, mul(comb_a, comb_b));
    ans = add(ans, mul(add(A, 1), add(B, 1)));
    ans = add(ans, mul(add(A, 1), mul(comb_b, choose2(add(B, 1)))));
    ans = add(ans, mul(add(B, 1), mul(comb_a, choose2(add(A, 1)))));
    cout << ans << endl;
}
 
int main()
{
    int t;
    cin >> t;
    for(int i = 0; i < t; i++) solve();    
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
 
typedef long long li;
typedef pair<int, int> pt;
 
const int INF = int(1e9);
const li INF64 = li(1e18);
 
vector<int> Tadd, Tmax;
 
int getmax(int v) {
	return Tmax[v] + Tadd[v];
}
void push(int v) {
	Tadd[2 * v + 1] += Tadd[v];
	Tadd[2 * v + 2] += Tadd[v];
	Tadd[v] = 0;
}
void upd(int v) {
	Tmax[v] = max(getmax(2 * v + 1), getmax(2 * v + 2));
}
void addVal(int v, int l, int r, int lf, int rg, int val) {
	if (l == lf && r == rg) {
		Tadd[v] += val;
		return;
	}
	push(v);
	int mid = (l + r) >> 1;
	if (lf < mid)
		addVal(2 * v + 1, l, mid, lf, min(mid, rg), val);
	if (rg > mid)
		addVal(2 * v + 2, mid, r, max(lf, mid), rg, val);
	upd(v);
}
int getMax(int v, int l, int r, int lf, int rg) {
	if (l == lf && r == rg)
		return getmax(v);
	push(v);
	int mid = (l + r) >> 1;
	int ans = -1;
	if (lf < mid)
		ans = max(ans, getMax(2 * v + 1, l, mid, lf, min(mid, rg)));
	if (rg > mid)
		ans = max(ans, getMax(2 * v + 2, mid, r, max(lf, mid), rg));
	upd(v);
	return ans;
}
 
int n;
vector<int> a;
 
inline bool read() {
	if(!(cin >> n))
		return false;
	a.resize(n);
	fore (i, 0, n)
		cin >> a[i];
	return true;
}
 
inline void solve() {
	vector<int> ask(n, 0);
	int mx = -1;
	for (int i = n - 1; i >= 0; i--) {
		if (a[i] > mx) {
			ask[i] = 1;
			mx = a[i];
		}
	}
	vector<int> left;
	fore (i, 0, n) {
		if (left.empty() || a[left.back()] > a[i])
			left.push_back(i);
	}
 
	Tadd.assign(4 * n, 0);
	Tmax.assign(4 * n, 0);
 
	auto compY = [](int i, int j) {
		if (a[i] != a[j])
			return a[i] < a[j];
		return i > j;
	};
	vector<int> ordToAdd(n);
	iota(ordToAdd.begin(), ordToAdd.end(), 0);
	sort(ordToAdd.begin(), ordToAdd.end(), compY);
 
	auto getSeg = [&left](int id) {
		int lf = upper_bound(left.begin(), left.end(), id, [&left](int v, int i) {
			return a[v] > a[i];
		}) - left.begin();
		int rg = lower_bound(left.begin(), left.end(), id) - left.begin();
		return pt(lf, rg);
	};
	auto addToSeg = [&left, &getSeg](int id, int val) {
		auto [lf, rg] = getSeg(id);
		if (lf < rg)
			addVal(0, 0, sz(left), lf, rg, val);
	};
 
	int ans = 0;
	int pos = 0;
	vector<int> added(n, 0);
	for (int i = n - 1; i >= 0; i--) {
		while (pos < n && !compY(i, ordToAdd[pos])) {
			if (ordToAdd[pos] <= i) {
				addToSeg(ordToAdd[pos], 1);
				added[ordToAdd[pos]] = 1;
			}
			pos++;
		}
		if (ask[i]) {
			auto [lf, rg] = getSeg(i);
			ans = max(ans, 1 + (lf < rg ? getMax(0, 0, sz(left), lf, rg) : 0));
		}
		if (added[i]) {
			addToSeg(i, -1);
			added[i] = 0;
		}
	}
	cout << ans << endl;
}
 
int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int t; cin >> t;
	while(t--) {
		(read());
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}