Problem G
Equations
Input: Standard Input

Output: Standard Output

Find the number of solutions, the equation ∑X_i = s have, if A_i≤X_i≤B_i for each i = 1…n.

For example,

X₁ + X₂ + X₃ = 10

-1 ≤ X₁ ≤ 3

2 ≤ X₂ ≤ 4

6 ≤ X₃ ≤ 7

The above set of equations has 6 solutions. They are: {1,4,7}, {0,3,7}, {0,4,6}, {1,2,7}, {1,3,6} and {2,2,6}.

You are given n the number of variables and the range of them. Your task is to calculate the number of solutions of that equation.

Input:

First line of the Input contains T (≤50) the number of test cases. Then T test cases follow. First line of each test case contains 2 integer n (1≤n≤10) and s (-50000 ≤ s ≤ 50000). Next n lines each contain 2 integers describing the range of each variable. The i^th line A_i and B_i (‑10000 ≤ A_i ≤ B_i ≤10000). X_i can take any integral value in the range [A_i, B_i].

Output:

For each test case output contains one integer denoting the number of solutions of the given equations. Output the value modulo 200003.

Sample Input	Sample Output
1 3 10 -1 3 2 4 6 7	6

---

Problemsetter: Abdullah Al Mahmud

Special Thanks To: Istiaque Ahmed & Mohammad Mahmudur Rahman