#include <iostream>
#define int long long

using namespace std;

const int N = 2510, mod = 2333;

int T, n, k;
int c[N][N], f[N][N];

inline void init()
{
    // puts("Function \"Init\" has been called");
    for (int i = 0; i < N; i ++ ) // init C
        for (int j = 0; j <= i; j ++ )
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    for (int i = 0; i < N; i ++ ) // init f
        for (int j = 0; j < N; j ++ )
            if (!j) f[i][j] = 1;
            else f[i][j] = (f[i][j - 1] + c[i][j]) % mod; // f is C's prefix sum
}

inline int lucas(int a, int b)
{
    // puts("Function \"Lucas\" has been called");
    if (a < mod && b < mod) return c[a][b];
    return lucas(a / mod, b / mod) * c[a % mod][b % mod] % mod;
}

inline int get(int a, int b)
{
    // puts("Function \"Get\" has been called");
    if (a < mod && b < mod) return f[a][b];
    return (f[a % mod][mod - 1] * get(a / mod, b / mod - 1) % mod\
     + lucas(a / mod, b / mod) * f[a % mod][b % mod] % mod) % mod;
    // return (get(a % mod, mod - 1) * get(a / mod, b / mod - 1) % mod\
    // + lucas(a / mod, b / mod) * get(a % mod, b % mod) % mod) % mod;
}

signed main()
{
    init();

    scanf("%lld", &T);
    while (T -- )
    {
        scanf("%lld%lld", &n, &k);
        // cout << n << ' ' << k << endl;
        printf("%lld\n", get(n, k) % mod);
    }

    return 0;
}