Factorial to Square

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Given a positive integer n, we want to remove some values between 1 and n such that the product of the remaining ones is a perfect square number (i.e. the product = x * x, for some integer x). Meanwhile, we also want to maximize the product. Therefore, we are interested in the number of ways to remove some values to achieve the maximum perfect square product. The answer may be very large, and therefore, you just need to output its remainder by dividing m.
We define the product of an empty set as 1.
Input
The first line contains an integer T denoting the total number of test cases.
In each test case, there are two positive integers n and m in a line separated by a single space.
Output
For each test case, output the answer per line.
Constraints
 1 <= T <= 10
 1 <= n <= 3,000
 1 <= m <= 10^{9} + 7
Example
Input: 2 2 10 5 10 Output: 2 2
Explanation
In the first case, you can either remove 2 or remove both 1 and 2. In the second case, you can either remove 2, 3, 5 or remove 1, 2, 3, 5.
Author:  shangjingbo 
Editorial  http://discuss.codechef.com/problems/FSFSFS 
Tags  cook63, dp+bitmask, mediumhard, shangjingbo 
Date Added:  9102015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
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. 