D. Binary Subsequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an integer $$$n$$$, your task is to find the expectation of the length of the longest non-decreasing subsequence in a binary string, i.e. a sequence consisting of either $$$\texttt{0}$$$ or $$$\texttt{1}$$$, of length $$$n$$$.

A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements. For example, $$$[1,2,3]$$$ is a subsequence of $$$[1,4,2,5,3]$$$, while $$$[1,3,2]$$$ is not. In the context of a binary string, a non-decreasing subsequence will consist of a series (possibly zero) of $$$\texttt{0}$$$s followed by a series (possibly zero) of $$$\texttt{1}$$$s.

You should output the answer modulo $$$M$$$. That is, representing the answer as a rational fraction $$$\frac{a}{b}$$$, your output should be the smallest non-negative integer $$$x$$$ that satisfies $$$a \equiv bx \pmod{M}$$$, where $$$M$$$ is a given prime number.

Input

The first line contains an integer $$$T$$$ ($$$1\le T \le 1000$$$), denoting the number of test cases.

Each test case contains two integers $$$n, M$$$ ($$$1\le n \le 5000$$$, $$$10^8\le M \le 10^9$$$). $$$M$$$ is prime.

It is guaranteed that $$$\sum n \le 5000$$$ over all test cases.

Output

For each test case, output the answer modulo $$$M$$$ in a single line.

Example
Input
2
2 998244353
3 998244853
Output
249561090
499122429
Note

For $$$n = 2$$$, we have four sequences: $$$\texttt{00},\texttt{01},\texttt{10},\texttt{11}$$$, each with a probability of $$$\frac{1}{4}$$$. The lengths of their longest non-decreasing subsequences are $$$2, 2, 1, 2$$$, respectively. Therefore, the answer is $$$\frac{1}{4} \times (2 + 2 + 1 + 2) = \frac{7}{4}$$$.