//Given a floor of size n x m. Find the number of ways to tile the floor with tiles of size 1 x m . A tile can either be placed horizontally or vertically.
#include <bits/stdc++.h>
#define ll long long
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

using namespace std;

//Number of ways of tiling MXN floor with 1XM tiles
int tile(int n,int m){
	if(n < m)
		return 1;

	if(n == m){
		return 2;
	}

	return tile(n-1,m) + tile(n-m,m);
}

int main() {
	fastio;
	int t;
	cin >> t;
	while(t--){
	int n,m;
	cin >> n >> m;

	cout << tile(n,m) << endl;
	}
	

	return 0;
}