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 watermelon i is strictly lighter than watermelon j;
• > if watermelon i is strictly heavier than watermelon j;
• ? 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).