13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T668,

Dreamoon likes sequences very much. So he created a problem about the sequence that you can't find in OEIS:

You are given two integers $$$d, m$$$, find the number of arrays $$$a$$$, satisfying the following constraints:

The length of $$$a$$$ is $$$n$$$, $$$n \ge 1$$$
$$$1 \le a_1 \lt a_2 \lt \dots \lt a_n \le d$$$
Define an array $$$b$$$ of length $$$n$$$ as follows: $$$b_1 = a_1$$$, $$$\forall i \gt 1, b_i = b_{i - 1} \oplus a_i$$$, where $$$\oplus$$$ is the bitwise exclusive-or (xor). After constructing an array $$$b$$$, the constraint $$$b_1 \lt b_2 \lt \dots \lt b_{n - 1} \lt b_n$$$ should hold.

Since the number of possible arrays may be too large, you need to find the answer modulo $$$m$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) denoting the number of test cases in the input.

Each of the next $$$t$$$ lines contains two integers $$$d, m$$$ ($$$1 \leq d, m \leq 10^9$$$)

Dreamoon Likes Sequences

Examples