#include <bits/stdc++.h>
using namespace std;
#define MAXK 330
#define MOD 1234567891
unsigned int f[MAXK+1][MAXK+1];
unsigned int pwr(int x, int n) {
if (!n) return 1;
unsigned int y = pwr(x, n>>1);
y = (1ULL * y * y) % MOD;
if (n & 1) y = (1ULL * x * y) % MOD;
return y;
}
void precompute() {
f[0][1] = 1;
for (int i = 1; i < MAXK; i++) {
long long s = 0;
for (int j = 2; j <= i+1; j++) {
f[i][j] = (((1ULL * i * pwr(j, MOD-2)) % MOD) * 1ULL * f[i-1][j-1]) % MOD;
s += f[i][j];
}
f[i][1] = (MOD + 1 - (s % MOD)) % MOD;
}
}
unsigned int calc(int n, int k) {
unsigned int ans = 0;
for (int i = k+1; i >= 0; i--) {
ans = (1ULL * n * ans + f[k][i]) % MOD;
}
return ans;
}
int main() {
precompute();
cout << calc(2, 3) << endl;
int t, n, k;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &k);
int ans = (1ULL * (n+1) * calc(n, k)) % MOD;
ans = (1LL * ans - calc(n, k+1) + MOD) % MOD;
printf("%d\n", ans);
// n = 2, k = 3 => 3 *
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIE1BWEsgMzMwCiNkZWZpbmUgTU9EIDEyMzQ1Njc4OTEKCnVuc2lnbmVkIGludCBmW01BWEsrMV1bTUFYSysxXTsKCnVuc2lnbmVkIGludCBwd3IoaW50IHgsIGludCBuKSB7CglpZiAoIW4pCXJldHVybiAxOwoJdW5zaWduZWQgaW50IHkgPSBwd3IoeCwgbj4+MSk7Cgl5ID0gKDFVTEwgKiB5ICogeSkgJSBNT0Q7CglpZiAobiAmIDEpCXkgPSAoMVVMTCAqIHggKiB5KSAlIE1PRDsKCXJldHVybiB5Owp9Cgp2b2lkIHByZWNvbXB1dGUoKSB7CglmWzBdWzFdID0gMTsKCWZvciAoaW50IGkgPSAxOyBpIDwgTUFYSzsgaSsrKSB7CgkJbG9uZyBsb25nIHMgPSAwOwoJCWZvciAoaW50IGogPSAyOyBqIDw9IGkrMTsgaisrKSB7CgkJCWZbaV1bal0gPSAoKCgxVUxMICogaSAqIHB3cihqLCBNT0QtMikpICUgTU9EKSAqIDFVTEwgKiBmW2ktMV1bai0xXSkgJSBNT0Q7CgkJCXMgKz0gZltpXVtqXTsKCQl9CgkJZltpXVsxXSA9IChNT0QgKyAxIC0gKHMgJSBNT0QpKSAlIE1PRDsKCX0KfQoKdW5zaWduZWQgaW50IGNhbGMoaW50IG4sIGludCBrKSB7Cgl1bnNpZ25lZCBpbnQgYW5zID0gMDsKCWZvciAoaW50IGkgPSBrKzE7IGkgPj0gMDsgaS0tKSB7CgkJYW5zID0gKDFVTEwgKiBuICogYW5zICsgZltrXVtpXSkgJSBNT0Q7Cgl9CglyZXR1cm4gYW5zOwp9CgppbnQgbWFpbigpIHsKCXByZWNvbXB1dGUoKTsKCWNvdXQgPDwgY2FsYygyLCAzKSA8PCBlbmRsOwoJaW50IHQsIG4sIGs7CglzY2FuZigiJWQiLCAmdCk7Cgl3aGlsZSAodC0tKSB7CgkJc2NhbmYoIiVkJWQiLCAmbiwgJmspOwoJCWludCBhbnMgPSAoMVVMTCAqIChuKzEpICogY2FsYyhuLCBrKSkgJSBNT0Q7CgkJYW5zID0gKDFMTCAqIGFucyAtIGNhbGMobiwgaysxKSArIE1PRCkgJSBNT0Q7CgkJcHJpbnRmKCIlZFxuIiwgYW5zKTsKCQkvLyBuID0gMiwgayA9IDMgPT4gMyAqIAoJfQoJcmV0dXJuIDA7Cn0=