B. Dreamoon любит последовательности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Dreamoon очень любит последовательности. Поэтому он придумал задачу про последовательность, которую нельзя найти на OEIS:

Вам дано два целых числа $$$d, m$$$, вам нужно найти количество массивов $$$a$$$, удовлетворяющих следующим ограничениям:

  • Длина $$$a$$$ равна $$$n$$$, $$$n \ge 1$$$
  • $$$1 \le a_1 < a_2 < \dots < a_n \le d$$$
  • Рассмотрим следующий массив $$$b$$$ длины $$$n$$$: $$$b_1 = a_1$$$, $$$\forall i > 1, b_i = b_{i - 1} \oplus a_i$$$, где $$$\oplus$$$ это побитовое исключащее или (xor). После построения массива $$$b$$$, должно выполняться ограничение $$$b_1 < b_2 < \dots < b_{n - 1} < b_n$$$.

Так как количество возможных массивов может быть слишком большим, вам нужно найти его по модулю $$$m$$$.

Входные данные

В первой строке записано целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) обозначающее количество наборов входных данных в задаче.

Каждая из следующих $$$t$$$ строк содержит два целых числа $$$d, m$$$ ($$$1 \leq d, m \leq 10^9$$$).

Обратите внимание, что $$$m$$$ необязательно простое!

Выходные данные

Для каждого набора входных данных, выведите количество массивов $$$a$$$, удовлетворяющих всем ограничениям, по модулю $$$m$$$.

Пример
Входные данные
10
1 1000000000
2 999999999
3 99999998
4 9999997
5 999996
6 99995
7 9994
8 993
9 92
10 1
Выходные данные
1
3
5
11
17
23
29
59
89
0