Sequence

Problem Description

Xiaoqi loves sequences very much, so she made a sequence problem.

Given two integers $d, m$, find the number of sequences $a$ satisfying:

• the length $n$ of sequence $a$ is at least $1$ ($n \ge 1$);
• $1 \le a_1 < a_2 < \dots < a_n \le d$;
• define an array $c$ of length $n$: $c_1 = a_1$, and for all $i > 1$, $c_i = c_{i-1} \oplus a_i$, where $\oplus$ denotes binary XOR. The array $c$ must satisfy $c_1 < c_2 < \dots < c_n$.

How many such sequences are there? Since the result may be large, output the answer modulo $m$.

Input Format

The first line contains an integer $t$ ($1 \le t \le 100$), the number of test cases.

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

Note: $m$ is not necessarily prime.

Output Format

Output $t$ lines, each containing one integer: the answer.

Sample Input

3
5 999996
6 99995
7 9994

Sample Output

17
23
29

Constraints

For all data, $1 \le t \le 100$ and $1 \le d, m \le 10^9$.