// File Name: 1119.cpp
// Author: bo_jwolf
// Created Time: 2014年02月05日 星期三 15时01分32秒

#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>

using namespace std;

const int maxn = 1005;
int num[ maxn ];

int main(){
	int Case, n, m;
	cin >> Case;
	while( Case-- ){
		memset( num, 0, sizeof( num ) );
		cin >> n >> m;
		for( int i = 0; i <= n; ++i ){
			if( i < m ){
				num[ i ] = pow( 2, i );
			}
			else if( i == m ){
				num[ i ] = pow( 2, i ) - 1;
			}
			else if( i == m + 1 ){
				num[ i ] = 2 * num[ i - 1 ] - 1;
			}
			else{
				num[ i ] = 2 * num[ i - 1 ] - num[ i - m - 1 ];
			}
		}
		cout << num[ n ] << endl;
	}
return 0;
}

化学品问题 I