Define a sequence of integers (a) valid if and only if (\forall 1 \le i \le n, 0 \le a_i \le i). Define the weight (f(a)) of a valid sequence (a) of length (n): Initially, a token is placed at each integer point in the closed segment (1, n) on the number axis. Perform (n) operations in sequence. During the (i)-th operation, if (a_i \ne 0), remove a token in the closed segment (a_i, i) that has not been removed; otherwise, do nothing. (f(a)) is the number of ways to remove tokens. Two ways are considered different if there exists a (t) such that the positions of the tokens removed by the two ways are different at the (t)-th operation. For example, (f(0, 2, 1) = 2), because we can remove tokens on (2, 1) or (2, 3) in sequence. JT gives you two integers (n, m) and asks you to find the sum of the weight s over all ((n + 1)!) valid sequences of length (n). Since the answer may be too large, print it modulo (m). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 1000)). The description of the test cases follows. The only line of each test case contains two integers (n) and (m) ((1 \le n \le 5000, 10^8 \le m \le 1.01 \cdot 10^9)) — the length of valid sequences, and the modulus. It is guaranteed that the sum of (n^2) over all test cases does not exceed (2.5 \cdot 10^7). For each test case, output an integer — the sum of the weight s over all ((n + 1)!) valid sequences of length (n), modulo (m). In the first test case, valid sequences are (0) and (1), and the answer is (f(0) + f(1) = 1 + 1 = 2). In the second test case, valid sequences are (0, 0, 0, 1, 0, 2, 1, 0, 1, 1, 1, 2). The weight of (0, 1) is (2), and the others are (1), so the answer is (5 \cdot 1 + 1 \cdot 2 = 7).