#include <iostream>
#include <vector>
using namespace std;
 
vector<long long int> dp;
const unsigned int M = 1000000007;
 
int helper(long long int start, long long int N, int K) {
	cout<<start<<" "<<N<<" "<<K<<"\n";
	if(start>N) return 0;
	if(start==N) return 1;
	if(dp[start]!=0) {
		return dp[start];
	}
 
	int ans=0;
	ans=(helper(start+1, N, K)%M + helper(start+2, N, K)%M)%M;
	if(K>0) {
		K--;
		ans=(ans%M+helper(start+3, N, K)%M)%M;
	}
 
	return dp[start]=ans;
}
 
int main() {
	int T;
	cin>>T;
	while(T--) {
		long long int N;
		int K;
		cin>>N>>K;
		dp.clear();
		dp.resize(N+5, 0);
		cout<<helper(0, N, K)<<"\n";
	}
 
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdmVjdG9yPGxvbmcgbG9uZyBpbnQ+IGRwOwpjb25zdCB1bnNpZ25lZCBpbnQgTSA9IDEwMDAwMDAwMDc7CgppbnQgaGVscGVyKGxvbmcgbG9uZyBpbnQgc3RhcnQsIGxvbmcgbG9uZyBpbnQgTiwgaW50IEspIHsKCWNvdXQ8PHN0YXJ0PDwiICI8PE48PCIgIjw8Szw8IlxuIjsKCWlmKHN0YXJ0Pk4pIHJldHVybiAwOwoJaWYoc3RhcnQ9PU4pIHJldHVybiAxOwoJaWYoZHBbc3RhcnRdIT0wKSB7CgkJcmV0dXJuIGRwW3N0YXJ0XTsKCX0KCQoJaW50IGFucz0wOwoJYW5zPShoZWxwZXIoc3RhcnQrMSwgTiwgSyklTSArIGhlbHBlcihzdGFydCsyLCBOLCBLKSVNKSVNOwoJaWYoSz4wKSB7CgkJSy0tOwoJCWFucz0oYW5zJU0raGVscGVyKHN0YXJ0KzMsIE4sIEspJU0pJU07Cgl9CgkKCXJldHVybiBkcFtzdGFydF09YW5zOwp9CgppbnQgbWFpbigpIHsKCWludCBUOwoJY2luPj5UOwoJd2hpbGUoVC0tKSB7CgkJbG9uZyBsb25nIGludCBOOwoJCWludCBLOwoJCWNpbj4+Tj4+SzsKCQlkcC5jbGVhcigpOwoJCWRwLnJlc2l6ZShOKzUsIDApOwoJCWNvdXQ8PGhlbHBlcigwLCBOLCBLKTw8IlxuIjsKCX0KCQoJcmV0dXJuIDA7Cn0=

MQo3IDE=

1
7 1