Dãy yêu thích của Dreamoon

Cho hai số nguyên $d$ và $m$. Hãy đếm số dãy $a$ thỏa mãn đồng thời các điều kiện sau:

• Độ dài của $a$ là $n$, với $n\ge 1$.
• $1\le a_1<a_2<\dots <a_n\le d$.
• Xét dãy $b$ có cùng độ dài $n$ được định nghĩa bởi $b_1=a_1$ và $b_i=b_{i-1}\oplus a_i$ với mọi $i>1$, trong đó $\oplus$ là phép XOR (hoặc loại trừ) trên bit. Khi đó dãy $b$ phải thỏa mãn $b_1<b_2<\dots <b_n$.

Vì số dãy hợp lệ có thể rất lớn, hãy in ra kết quả theo modulo $m$.

Lưu ý rằng $m$ không nhất thiết là số nguyên tố.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên $t$ — số lượng bộ dữ liệu.
• $t$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $d$ và $m$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số dãy $a$ hợp lệ, lấy theo modulo $m$.

Ràng buộc

• $1\le t\le 100$
• $1\le d,m\le {10}^9$

Ví dụ