#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1234567891;
int K, n;
struct arr {
	int a[35][35];
	arr() {
		memset(a, 0, sizeof a);
	}
	void print() {
		for (int i = 1; i <= K + 1; i++) {
			for (int j = 1; j <= K + 1; j++) {
				printf("%lld ", a[i][j]);
			}
			printf("\n");
		}
	}
	arr operator*(const arr& T) const {
		arr cur;
		int r;
		for (int i = 1; i <= K + 1; ++i)
			for (int k = 1; k <= K + 1; ++k) {
				r = a[i][k];
				for (int j = 1; j <= K + 1; ++j)
					cur.a[i][j] += T.a[k][j] * r, cur.a[i][j] %= mod;
			}
		return cur;
	}
	arr operator^(int x) const {
		arr cur, res;
		for (int i = 1; i <= K + 1; ++i) cur.a[i][i] = 1;
		for (int i = 1; i <= K + 1; ++i)
			for (int j = 1; j <= K + 1; ++j) res.a[i][j] = a[i][j] % mod;
		while (x) {
			if (x & 1) cur = cur * res;
			res = res * res;
			x >>= 1;
		}
		return cur;
	}
} A, F;
void work(int k) {
	memset(A.a,0,sizeof A.a);
	memset(F.a,0,sizeof F.a);
	for (int i = 1, j = k - 1; i <= k; i++, j--) {
		A.a[i][i] = i;
		A.a[i][i + 1] = j;
	}
	if(k==1&&n==1){
		puts("1");
		return;
	}
	A.a[k+1][k+1] = A.a[k][k+1] = 1;
	F.a[1][1] = k;
	F = F * (A ^ (k + 1));
	printf("%lld\n", F.a[1][k+1]);
}
signed main() {
	int t;
	cin>>t;
	while(t--){
		scanf("%lld", &n);
		scanf("%lld", &K);
		work(K);
	}
	return 0;
}