Description

The inventor SHTSC, who once created the Brain-hole Therapy Device and the Super Particle Cannon, has now unveiled his new invention: Super Particle Cannon · Modified — a mysterious device that can fire particle streams with much greater power.

Compared with the Super Particle Cannon, Super Particle Cannon · Modified has a fundamental increase in power. It has two parameters $n, k$. It fires, at each position $i$ numbered from $0$ to $k$ inclusive, a particle stream with power $C_{n}^{i} \bmod 2333$.

Now SHTSC gives you the parameters of his Super Particle Cannon · Modified. Please compute the remainder modulo $2333$ of the sum of the powers of the particle streams it fires.

Input Format

The first line contains an integer $t$ denoting the number of test cases.

Then follow $t$ lines. Each line contains two integers $n, k$, as described above.

Output Format

Output $t$ lines. Each line contains one integer: the value of the sum of the powers modulo $2333$.

3
5 5
10 7
1145 14

32
968
763

Hint

For $10\%$ of the testdata, $t = 1$, $n, k \le 1000$.
For $30\%$ of the testdata, $t = 1$, $n, k \le 1000000$.
For $50\%$ of the testdata, $t = 1$, $n \le 10^{18}$, $k \le 1000$.
For $70\%$ of the testdata, $t = 100$, $n, k \le 10^{18}$.
For $100\%$ of the testdata, $t = 100000$, $n, k \le 10^{18}$.

Translated by ChatGPT 5