In the mystical village of Westasia, there's a tradition during the weekly Wookiee Festival where villagers gather to play a game called Watermelon Warfare.
In Watermelon Warfare, the players are given n
watermelons, and the players work together to find the heaviest watermelon. Initially, the weights of the watermelons are unknown, but it is guaranteed that the weights are distinct. The players then weigh the watermelons against each other with a weighing scale to gather information about the weights.
Wesley and Wendy would like to analyze this game more deeply.
They figured that at any point in the game, the partial information can be encoded as follows. First, number the watermelons 1
to n
. Then, for each pair (i, j)
such that 1 ≤ i < j ≤ n
, let cmpi,j
be the information about the comparison of watermelons i
and j
. Specifically, it is one of:
<
if watermeloni
is strictly lighter than watermelonj
;>
if watermeloni
is strictly heavier than watermelonj
;?
if we don't have information either way.
Thus, there are 3
possible values of cmpi,j
, and there are 3n(n-1)/2
possible ways to assign the values of all cmpi,j
.
For each such assignment A
, let W(A)
be the number of watermelons i
such that it is consistent for watermelon i
to be the heaviest watermelon given the assignment A
. Note that if A
is "inconsistent", then W(A) = 0
.
Help Wesley and Wendy find the sum of W(A)
across all 3n(n-1)/2
assignments! However, because this number may be large, you only need to find it modulo a given prime number p
.
Input Format
The first line contains a single integer t
, the number of test cases. The descriptions of t
test cases follow.
Each test case consists of one line containing two space-separated integers n
and p
.
Output Format
For each test case, print a single line containing the sum of W(A)
across all assignments A
, modulo p
.
Constraints
1 ≤ t ≤ 3
1 ≤ n ≤ 2000
108 < p < 109
p
is prime
Sample
Input
3 3 100000007 5 100000007 7 100000007
Output
36 43440 94113232
Explanation
For n = 3
, there are 33(3-1)/2 = 27
possible assignments A
. The sum of W(A)
across all these assignments is 36
(modulo 100000007
).