5827：Rikka with Parenthesis

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

Correct parentheses sequences can be defined recursively as follows:
1.The empty string "" is a correct sequence.
2.If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence.
3.If "X" is a correct sequence, then "(X)" is a correct sequence.
Each correct parentheses sequence can be derived using the above rules.
Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))".

For a parentheses sequence, Rikka can make some operations on it. Each time she can choose two indices L and R such that L <= R. The operation modifies the characters on indices from L to R, inclusive. First, the order of these characters is reversed. Then, each character is toggled to the opposite one. That is, each '(' in the specified range changes to a ')' and vice versa.

The value of a parentheses sequence is the minimal number of the operations to change it to a correct parentheses sequence. If it is impossible, the value of the sequence is equal to 10^100.

For example, The value of '()((' is 1, the value of '()()' is 0 and the value of '(((' is 10^100.

Now Yuta shows two numbers n and m, For each K in [0,n], he wants to know the number of the different parentheses sequence of length n which has value K. The answer may be very large, he only wants to know the answer module m.

It is too difficult for Rikka. Can you help her?

The first line contains a number t(1<=t<=10), the number of the testcases. For each testcase, the first line contains two integers n,m (1<=n<=10^6,1<=m<=10^9).

For each testcase, print a line contains a single number. Let A[i] be the answer when K=i, you need to output $(\sum_{i=0}^n (i+1) \times A[i]) \mod m$.