URI Online Judge | 1381

Diophantine Equations

By Wanderley Guimarães, IME-USP Brazil
Timelimit: 3

Diophantus of Alexandria lived in the third century AD and is considered by many as the "father of algebra". His book "Arithmetica" was about the solution of algebraic equations with integer coefficients for which it also seeks integer solutions. These equations are known as Diophantine equations. A great scholar of Diophantus' work was Pierre de Fermat, a known French mathematician.

In this problem you must solve a class of Diophantine equations of the type x1 + x2 + ... +xn = C. That is, given integers N and C, determine how many non-negative integer solutions exist for the equation x1 + x2 + ... +xn = C, where0 ≤ xi ≤ C for all i = 1, 2, ... , N.

Input

The input is composed of several test cases. The first line of input contains an integer T indicating the number of test cases. Each test case consists of a line containing two integers N and C (1 ≤ N, C ≤ 1000000). Due the possibility of this number be too big, so print it as module 1300031 (number % 1300031).

Output

For each test case print a line containing the number of integer solutions that satisfy the constraints.

Sample Input Sample Output

2
7 4
3 5

210
21