WAR ZONE

All submissions for this problem are available.
The Ministry of Defence (MoD) of Mighty Mouse Kingdom (MMK) needs to arrange defence forces in a battlefield to prevent possible attacks of Catland's army. The battlefield is a square grid of N rows and N columns. The cell in the i^{th} row and j^{th} column is denoted by (i,j), with 0 ≤ i, j ≤ N1.
The MoD wants to put exactly N cannons in cells of the grid. Each cannon can guard all the cells that are in the same column or same row as it is. To minimize the cost, the MoD decides that each row and each column should be guarded by exactly one cannon.
Of course not all ways of arranging the cannons are equally good strategically. A cannon in cell (i, j) is said to be in a safe position if:
 1 ≤ j ≤ N2
 The row coordinates of the cannons in the j1^{st} and j+1^{st} columns lie on the same side of the row coordinate i of the cannon (i,j). In other words, if we denote r_{k} to be the row position of the cannon in the k^{th} column, we should have either r_{j1} < i and r_{j+1} < i, or r_{j1} > i and r_{j+1} > i.
The Safety Index (SI) of the battlefield is the number of cannon in safe positions. Military strategists have pointed out that the SI must be at least K (K may vary depending on the weather, opponent's forces, etc.) in order to have a good defence of this important battlefield.
Compute the number of ways of arranging the cannons so that the SI is at least K.
Input
The first line contains t, the number of test cases (about 1000). Then t test cases follow. Each test case is described in a single line containing two numbers N and K (3 ≤ N ≤ 2000, 0 ≤ K ≤ N2).
Output
For each test case, print a single line containing the number of ways of arranging the cannons so that the Safety Index is at least K. Since the result may be very large, you only need to print the remainder of the result when dividing by 30041975.
Example
Input: 3 3 1 4 1 8 5 Output: 4 22 13102
Output details
Case 1: There are four ways of arranging the cannons: put the cannon at positions {(1,1), (2,3), (3,2)}, {(1,2), (2,3), (3,1)}, {(1,2), (2,1), (3,3)}, or {(1,3), (2,1), (3,1)}. The cannon in the middle column is always in the safe position.
Author:  cognizance2016 
Tags  cognizance2016 
Date Added:  30012016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 