The inventor SHTSC, who once invented the brain-hole therapy device and the super particle cannon, has unveiled his new invention: the Super Particle Cannon Kai—a mysterious device capable of firing a more powerful particle stream.

Compared to the super particle cannon, the Super Particle Cannon Kai has a fundamental improvement in power. It has three parameters $n$, $k$, and an implied third parameter. It fires a particle stream with power $C(n, i) \pmod{2333}$ at each position $i$ from $0$ to $k$.

Now, SHTSC has provided the parameters for his Super Particle Cannon Kai. You are asked to calculate the sum of the powers of the particle streams fired, modulo $2333$.

Input

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

Following this are $t$ lines, each containing two integers $n$ and $k$, as described in the problem statement.

Output

For each test case, output a single integer on a new line, representing the sum of the powers of the particle streams modulo $2333$.

Constraints

• For $10\%$ of the data: $n, k \le 1000$.
• For $30\%$ of the data: $n, k \le 10^6$.
• For $50\%$ of the data: $n \le 10^{18}$, $k \le 10^6$, $t = 1$.
• For $70\%$ of the data: $t \le 100$.
• For $100\%$ of the data: $n, k \le 10^{18}$, $k \le n$, $t \le 10^5$.

Examples

Input 1

1
5 5

Output 1

32

Input 2

1
10 7

Output 2

968

Input 3

5
100 50
101 51
102 52
103 53
104 54

Output 3

1487
2186
329
1901
254