Find the number of solutions, the equation For example: X1 + X2 + X3 = 10 −1≤X1 ≤3 2 ≤ X2 ≤ 4 6 ≤ X3 ≤ 7 ∑ Xi = s have, if Ai ≤ Xi ≤ Bi for each i = 1...n. 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 Ai and Bi (−10000 ≤ Ai ≤ Bi ≤ 10000). Xi can take any integral value in the range [Ai,Bi]. 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 1 3 10 -1 3 24 67 Sample Output 6