Dreamoon Likes Sequences
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 < a_2 < \dots < a_n \le d$$$  Define an array $$$b$$$ of length $$$n$$$ as follows: $$$b_1 = a_1$$$, $$$\forall i > 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 < b_2 < \dots < b_{n - 1} < b_n$$$ should hold. Since the number of possible arrays may be too large, you need to find the answer modulo $$$m$$$.
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$$$).Note that $$$m$$$ is not necessary the prime!
For each test case, print the number of arrays $$$a$$$, satisfying all given constrains, modulo $$$m$$$.
for q in range(int(input())):
    (n, m) = map(int, input().split())
    (st, ans) = (1, 1)
    while st <= n:
        ans *= min(st * 2 - st + 1, n - st + 2)
        st *= 2
    print((ans - 1) % m)
import math
a = [1] * 31
for i in range(31):
    a[i] = 1 << i
t = int(input())
while t:
    t -= 1
    (n, m) = map(int, input().strip().split(' '))
    k = int(math.log2(n))
    prod = 1
    for i in range(k):
        prod = prod * (a[i] + 1) % m
    r = n - a[k] + 1
    prod = prod * (r + 1) % m
    print(max((prod - 1) % m, 0))
import sys
lines = sys.stdin.readlines()
T = int(lines[0].strip())

def solve(d, m):
    s = bin(d)[2:]
    res = 1
    for i in range(len(s) - 1):
        res = (1 + 2 ** i) * res % m
    res = res * (d - 2 ** (len(s) - 1) + 2) % m
    res = (res - 1 + m) % m
    print(res)
for t in range(1, T + 1):
    (d, m) = map(int, lines[t].strip().split(' '))
    solve(d, m)